Given a graph $G = (V, E, w)$ and a source vertex $s$, find the shortest (minimum-weight) path from $s$ to every other vertex.
Dijkstra’s maintains a set of vertices whose final shortest distance is known. At each step, it selects the unvisited vertex with the smallest known distance and “relaxes” its neighbours.
dist[v] = shortest path distance from $s$ to $v$ for all verticesALGORITHM Dijkstra(graph, source)
dist ← Dictionary (all vertices → ∞)
dist[source] ← 0
pq ← PriorityQueue with (source, 0)
visited ← empty set
while NOT isEmpty(pq) do
(v, d) ← removeMin(pq) // vertex with smallest tentative distance
if v in visited then continue
add v to visited
for each (w, weight) in neighbours(graph, v) do
if dist[v] + weight < dist[w] then
dist[w] ← dist[v] + weight
insert (w, dist[w]) into pq
end if
end for
end while
return dist
Graph: A→B (1), A→C (4), B→C (2), B→D (5), C→D (1). Source: A.
| Step | v | dist[A] | dist[B] | dist[C] | dist[D] |
|---|---|---|---|---|---|
| Init | — | 0 | ∞ | ∞ | ∞ |
| 1 | A | 0 | 1 | 4 | ∞ |
| 2 | B | 0 | 1 | 3 | 6 |
| 3 | C | 0 | 1 | 3 | 4 |
| 4 | D | 0 | 1 | 3 | 4 |
Result: Shortest paths from A: B=1, C=3, D=4.
$O((V + E) \log V)$ with a binary heap priority queue.
Dijkstra’s is correct because of the greedy choice property: when a vertex is finalised (removed from the priority queue), its distance cannot improve further — this holds only when all weights are non-negative.
Fails with negative-weight edges. A negative edge could allow a shorter path through a “later” vertex, which Dijkstra’s would not reconsider.
Bellman-Ford relaxes all edges repeatedly, up to $V-1$ times, ensuring that shortest paths through any number of edges are found.
dist[v] = shortest path distance from $s$ to $v$, OR “negative cycle detected”ALGORITHM BellmanFord(graph, source)
dist ← Dictionary (all vertices → ∞)
dist[source] ← 0
for i ← 1 to |V| - 1 do // repeat |V|-1 times
for each edge (u, v, w) in graph do
if dist[u] + w < dist[v] then
dist[v] ← dist[u] + w
end if
end for
end for
// Check for negative-weight cycles
for each edge (u, v, w) in graph do
if dist[u] + w < dist[v] then
return "Negative cycle detected"
end if
end for
return dist
$O(V \cdot E)$ — significantly slower than Dijkstra’s.
After $k$ iterations, dist[v] gives the shortest path using at most $k$ edges. Since shortest simple paths use at most $V-1$ edges, $V-1$ iterations suffice.
If a $(V)$-th relaxation pass still improves a distance, there is a negative-weight cycle reachable from the source.
| Property | Dijkstra’s | Bellman-Ford |
|---|---|---|
| Edge weights | Non-negative only | Any (no negative cycles) |
| Time complexity | $O((V+E) \log V)$ | $O(VE)$ |
| Detects negative cycles | No | Yes |
| Strategy | Greedy | Relaxation (all edges) |
| Best for | Large graphs, non-negative weights | Graphs with negative weights |
EXAM TIP: Always state preconditions when choosing between these algorithms. Dijkstra’s requires non-negative weights; Bellman-Ford is slower but handles negative weights and detects negative cycles.