Date: February 18, 2026
Topic: Shortest Paths
<aside>
📌 SUMMARY:
To find the shortest path, we use the Bellman Ford method which allows for negative edges to exist.
A negative weight cycle can result from a loop that continuously reduces the cost of going through it.
We either output the shortest path, or if negative weight cycles exists, output those.
</aside>
Recall
We aim to find a way to compute the shortest path from a vertex to all other vertices in the graph. Using Djikstra’s algorithm is not ideal as it requires the weights to be positive.
Notes
Shortest Paths via DP
- Directed graphs $\vec{G}=(V,E)$ has edge weights $w(e)$
- Any undirected graph can be a directed graph by replacing each edge in an undirected graph with a pair of anti-parallel edges

$ad$ contains an anti-parallel edge
- Fix the start point $s$, ie $s \in V$
- Find the shortest distance from every point starting from $s$
- For $z \in V$, $\text{dist}(z)$ is the length of shortest path from $s$ to $z$
Dijkstra’s Algorithm
- Given $\vec{G}$ and $s \in V$, find $\text{dist}(z)$ for all $z \in V$
- It explores the graph in a similar manner to BFS which takes linear time $O(n+m)$
- $n$ is the number of vertices
- $m$ is the number of edges
- Since we have weights on the edges, we need to use a min heap or priority queue — each operation here takes $O(\log n)$ time
- So in total, Djikstra’s algorithm takes $O(n+m)O(\log n)$ time
- A drawback is that we need edge weights to be positive
Negative weight cycles may exist in the graph, where going through these cycles lead to decreasing costs.
For a given start vertex $s$, If such negative weight cycles exist and are reachable from $s$, then we should find them. If not, find for all $z \in V$.
Negative Weight Cycle

The yellow loop represents a negative weight cycle
- In the yellow loop, we can continuously move through it to keep getting a lower cost
- The shortest path, where we cannot repeat vertices, is $s \rightarrow b \rightarrow a \rightarrow d$ with a cost of $12$
- However, the shortest walk where we can repeat will end up infinitely looping
- Due to the negative weight cycle $a \rightarrow e \rightarrow b \rightarrow a$
- The sum of weights on this path is negative
- If negative weight cycles exist in the graph, we should find them
Redefining the Problem
- Given $\vec{G}$ with $w(e)$ and $s \in V$, find a negative weight cycle that can be reachable from $s$
- If there is no negative weight cycle, then we can just find for all $z \in V$
For our subproblem, we limit the number of edges on the path by the total number of vertices in the graph.
Dynamic Programming: Single Source Shortest Path
Given $\vec{G}$ with edge weights and $s \in V$ and assume no negative weight cycles
- Shortest path $P$ from $s$ to $z$ visits every vertex $\leq 1$ (visit each vertex at most once)
- Hence the shortest path is $|P| \leq n-1$ edges
Dynamic Programming Idea
- Idea: Use an increasing $i=0 \rightarrow n-1$ edges on the paths
- Number of edges we allow on the paths that we consider
- When $i=n-1$, the path can be at most $n-1$ edges
- For $0 \leq i \leq n-1$ and $z \in V$: let $D(i,z)$ be the length of shortest path from $s$ to $z$ using $\leq i$ edges
- We want to express $D(i,z)$ in terms of $D(i-1)$
To obtain the recurrence relation, we look at all ways to reach a penultimate vertex $y$ from the start vertex $s$. We use exactly $i-1$ edges to do this.
However for the shortest path $D(i,z)$ to $z$, we might not need to go through $y$ (i.e., no need to use $i=n-1$ edges. Hence, we need to consider the previous solution $D(i-1,z)$ as well which uses at most $i-1$ edges.
By minimizing these 2 expressions, the recurrence relation wrt. $D(i,z)$ is:
$\text{Cost}(i, z) = \min(\text{Cost prev. step}, \text{Cost neighbor } + \text{edge weight})$
Recurrence Relation
Subproblem
- For $0 \leq i \leq n-1$ and $z \in V$: let $D(i,z)$ be the length of shortest path from $s$ to $z$ using $\leq i$ edges
Base Case Definition
- $D(0,s)=0$ and for all $z \neq s$, $D(0,z) = \infty$
Recurrence

- For $i \geq 1$: look at the shortest path $s \rightarrow z$ using exactly $i$ edges
- Note this is slightly different from the subproblem definition, where we look at at most $i$ edges instead (we ignore this “at most” condition momentarily)
- We look at all possibilities for the penultimate vertex $y$ on the path and take the best (shortest or min.) of those choices
- We minimize over the choices for $y$
- $y$ must have an edge with $z$
- At the first step ($i=1$), $y = s$
- The total length of the path from $s$ to $z$ is $D(i-1,y)+w(y,z)$ and we seek to minimize this: $D(i, z) = \min_{y : \overrightarrow{yz} \in E} \{ D(i-1, y) + w(y, z) \}$
Looking for $\text{dist}(z)$
- When we look for the shortest path to $z$, is it not necessarily the shortest path using $i=n-1$ edges
- Might not necessarily use $n-1$ edges in the shortest path from $s$ to $z$ (so we don’t store the above minimization in $D(n-1,z)$)
Converting from $=i$ to $\leq i$ (back to at most)
- The previous solution $D(i-1,z)$ is already minimized from $s$ to $z$ using at most $i-1$ edges
- $D(i,z)$ using the formula above takes exactly $i$ edges
- Then we just need to minimize both to convert from exactly $i$ to at most $i$
Final Recurrence Formula
- Subproblem definiton: For $0 \leq i \leq n-1$ and $z \in V$: let $D(i,z)$ be the length of shortest path from $s$ to $z$ using $\leq i$ edges
- Base case: $D(0,s)=0$ and for all $z \neq s$, $D(0,z) = \infty$
- Recurrence relation: $\text{For } i \geq 1:
D(i, z) = \min \left\{ D(i-1, z), \min_{y} \{ D(i-1, y) + w(y, z) \} \right\}$
Date: February 18, 2026
Topic: Negative Weight Cycles
<aside>
📌 SUMMARY: Negative weight cycles can be found through the graph traveling table, where we expect the graph to converge by the $n-1$th row. If we have a subsequent $n$th row that has lower cost for some of the vertices, then negative weight cycles exist.
</aside>
Date: February 19, 2026
Topic: All-pairs Shortest Path