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

$ad$ contains an anti-parallel edge

$ad$ contains an anti-parallel edge

Dijkstra’s Algorithm


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

The yellow loop represents a negative weight cycle

Redefining the Problem


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

Dynamic Programming Idea


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

Base Case Definition

Recurrence

image.png

Looking for $\text{dist}(z)$

Converting from $=i$ to $\leq i$ (back to at most)

Final Recurrence Formula



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