3.6Single-source shortest paths
The idea
Dijkstra finds shortest paths from one source with non-negative weights by repeatedly finalising the closest vertex. Bellman-Ford also handles negative edges.
Think of it like this: A rumour spreading by the fastest route: the first time it reaches a town is its shortest time.
Why it exists
GATE asks the order of finalising and when Dijkstra fails.
How it works
- Set dist[source] = 0, the rest ∞.
- Pick the unfinished vertex with the least dist; it is final.
- Relax its outgoing edges.
- Bellman-Ford repeats "relax every edge" V − 1 times.
Worked example: Edges A→B = 4, A→C = 5, C→B = −3
Dijkstra finalises B at 4 before it sees the cheaper path through C (5 − 3 = 2). Negative edges break it.
Now play with it
- →Run Dijkstra on the sample graph and note the order the vertices turn green.
- →Read the edge-case table for negative weights.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- dist[A] = 0, all others ∞
- pick the closest unfinished vertex A (dist 0), it is final
- relax A→B: dist[B] = 0 + 4 = 4
- relax A→D: dist[D] = 0 + 2 = 2
- pick the closest unfinished vertex D (dist 2), it is final
- relax D→E: dist[E] = 2 + 4 = 6
- relax D→G: dist[G] = 2 + 8 = 10
- pick the closest unfinished vertex B (dist 4), it is final
- relax B→C: dist[C] = 4 + 6 = 10
- pick the closest unfinished vertex E (dist 6), it is final
- relax E→F: dist[F] = 6 + 1 = 7
- pick the closest unfinished vertex F (dist 7), it is final
- pick the closest unfinished vertex C (dist 10), it is final
- pick the closest unfinished vertex G (dist 10), it is final
Greedy: repeatedly finalise the closest vertex. O((V + E) log V) with a binary heap, O(V²) with an array. Fails with negative edges.
| Edge case | Result |
|---|---|
| A→B = 4, A→C = 5, C→B = −3 | true dist(B) = 2, but Dijkstra finalises B at 4: wrong with a negative edge |
| Negative edge, no negative cycle | Bellman-Ford is correct, O(VE) |
| Negative cycle reachable | Bellman-Ford reports it (a V-th pass still relaxes) |
| Unweighted graph | BFS is enough |
| DAG | relax in topological order, O(V + E), negative edges allowed |
Check yourself
Dijkstra with a binary heap on a graph with V vertices and E edges takes
Exam notes (the dense version)
Dijkstra repeatedly finalises the closest unvisited vertex; it needs non-negative weights; O((V + E) log V) with a heap, O(V²) with an array. Bellman-Ford relaxes every edge V − 1 times: O(VE), works with negative edges and detects negative cycles. For a DAG, relax in topological order: O(V + E). BFS suffices for unit weights.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.