Single-Source Shortest Paths: Dijkstra, Bellman-Ford and DAGs

The single-source shortest-paths problem asks for a shortest path from a source $s$ to every vertex of a weighted directed graph. Three algorithms cover the GATE syllabus cases: Dijkstra (nonnegative weights), Bellman-Ford (arbitrary weights, detects negative cycles), and a linear DAG scan that uses a topological order. Unweighted graphs reduce to BFS.

If a negative cycle is reachable from $s$ and can reach $v$, one sets $\delta(s,v) = -\infty$.

Every shortest-path algorithm initialises v.d <- infinity, s.d <- 0, and repeatedly relaxes edges. Correctness rests on the path-relaxation property: relaxing the edges of a shortest path in order produces the correct distance.

Pseudocode uses <- for assignment and a min-priority queue for Dijkstra.

Time. Binary heap: $O((V+E)\lg V)$. Fibonacci heap: $O(E + V \lg V)$. Array (dense): $O(V^2)$. Every vertex is inserted and extracted once ($|V|$ EXTRACT-MIN calls) and every edge is relaxed exactly once, when its tail is extracted ($|E|$ RELAX calls, at most $|E|$ DECREASE-KEY calls).

Settled vertices. In this CLRS form, line 9 relaxes every edge out of $u$, including edges into vertices already in $S$. With nonnegative weights such a relaxation never succeeds. With a negative edge it can lower the $d$ value of a settled vertex, but that improvement is never propagated, because the settled vertex is not extracted again. Many textbook variants skip settled vertices altogether. The four-vertex counterexample below defeats both forms.

Assumption that always holds for correctness. Every edge weight is nonnegative. Negative edges can make Dijkstra return wrong distances even without a negative cycle.

Time. $\Theta(VE)$. After $|V|-1$ passes every finite shortest path (at most $|V|-1$ edges) has been relaxed in order. A further improving edge witnesses a negative cycle.

How many passes are really needed. After pass $i$, every vertex that has a shortest path with at most $i$ edges holds its final distance, whatever the edge order. The order matters for speed: on the path $s \to a \to b \to c$ (weights 1), relaxing the edges in the order $(s,a), (a,b), (b,c)$ finishes in one pass, while the order $(b,c), (a,b), (s,a)$ needs all $|V|-1 = 3$ passes. A pass with no change means the distances are final, so an implementation may stop early. That shortcut does not replace the negative-cycle check, which still needs a pass after the last change.

Time. $\Theta(V+E)$. Negative weights are allowed because a DAG has no cycles at all. Negating every weight turns it into a longest-path algorithm, which is critical-path analysis in project networks. Longest simple paths are hard in general graphs, but easy in a DAG.

When $u$ is extracted, Dijkstra claims $u.d = \delta(s,u)$. The proof compares $u$ with the first unsettled vertex $y$ on a shortest path to $u$. Its settled predecessor has already relaxed it, so $d[y]=\delta(s,y)$. Nonnegative weights imply $\delta(s,y)\le\delta(s,u)$, giving $d[u]\le d[y]=\delta(s,y)\le\delta(s,u)\le d[u]$. A negative edge can make a later vertex offer a better path to an already settled vertex, breaking the claim. The counterexample in the worked examples settles $u$ at 2 and its successor $x$ at 3 before the negative edge $v\to u$ is seen; $x$ keeps the wrong value 3.

One safe exception. If only edges leaving the source $s$ are negative and there is no negative cycle, Dijkstra is still correct (CLRS Exercise 24.3-10): the key inequality $\delta(s,y) \le \delta(s,u)$ needs nonnegative weights only on the part of the path after $y$.

For every edge $(u,v)$, $\delta(s,v) \le \delta(s,u) + w(u,v)$, for any weights as long as no negative cycle is reachable from $s$. Relaxation enforces this locally until the estimates match the true distances.

Vertices $s,t,x,y,z$. Edges (weight): $s\to t:3$, $s\to y:5$, $t\to x:6$, $t\to y:2$, $y\to t:1$, $y\to x:4$, $y\to z:6$, $x\to z:2$, $z\to x:7$, $z\to s:3$. All weights positive.

Extract order from $s$: $s\,(0)$, $t\,(3)$, $y\,(5)$, $x\,(9)$, $z\,(11)$.

When $t$ is extracted, $t\to y$ offers $3+2 = 5$, a tie with the current 5, so $d[y]$ and $\pi[y] = s$ stay. $t\to x$ sets $d[x] = 9$. When $y$ is extracted, $y\to x$ offers $5+4 = 9$ (no change) and $y\to z$ sets $d[z] = 11$. Final distances: $s:0,t:3,y:5,x:9,z:11$. Relaxations that succeed: 4 ($t$, $y$ from $s$; $x$ from $t$; $z$ from $y$) out of 10 edge relaxations.

Vertices $s,u,v,x$; edges $s\to u:2$, $s\to v:4$, $v\to u:-3$, $u\to x:1$. There is no negative cycle. True distances: $\delta(s,u) = 4 - 3 = 1$ and $\delta(s,x) = 1 + 1 = 2$.

Dijkstra reports $d[x] = 3$, while $\delta(s,x) = 2$. Without the edge $u\to x$, the CLRS form would end with the correct $d[u] = 1$ by luck; the extra vertex makes the failure independent of the variant.

Take the three vertices $s, u, v$ with edges $s\to u:2$, $s\to v:4$, $v\to u:-3$, and add $u\to v:1$. Cycle $u\to v\to u$ has weight $-2$. After $|V|-1 = 2$ relaxation passes, the check pass still finds an improving edge, so Bellman-Ford returns FALSE.

Undirected negative edge. An undirected edge $\{u,v\}$ of weight $-1$ is two directed edges $u\to v$ and $v\to u$, which form a negative cycle of weight $-2$. So shortest paths with negative undirected edges are not well defined in this model.

Edges $s\to a:2$, $s\to b:6$, $a\to b:3$, $a\to c:4$, $b\to c:-2$; topological order $s, a, b, c$. One pass gives $d[a] = 2$, $d[b] = \min(6, 2+3) = 5$, $d[c] = \min(2+4, 5-2) = 3$. For the longest paths, run the same pass with negated weights: the longest $s$--$c$ path is $s\to a\to c$ of weight 6.

Related material. If $h(v)$ is a potential (for example $h(v)=\delta(s',v)$ from a super-source), the reduced weight $w_h(u,v)=w(u,v)+h(u)-h(v)$ preserves shortest paths and can eliminate negatives when no negative cycle exists. Johnson's all-pairs algorithm uses one complete Bellman-Ford run to build $h$, then Dijkstra from every vertex on $w_h$. Johnson is related material beyond the main syllabus treatment; the idea explains why "make weights nonnegative" is sometimes possible and why it fails when a negative cycle exists.

Writing the table in the answer sheet before tracing saves time when the question only says "compute shortest paths".