Plaintext
Dijkstra(Graph, source):
Initialize distance array dist[] to infinity for all nodes
Initialize visited set S to empty
dist[source] = 0
Insert all nodes into a Priority Queue Q, keyed by dist[]
while Q is not empty:
u = Q.extract_min() // Grab closest unvisited node
Add u to S // Permanently lock node u
for each neighbor v of u:
if v is not in S:
new_dist = dist[u] + weight(u, v)
if new_dist < dist[v]:
dist[v] = new_dist
Q.decrease_key(v, new_dist) // Update priority
return dist
Consider a 3-node graph with a source node \(A\):
Plaintext
Initialization:
dist = {A: 0, B: ∞, C: ∞}
Priority Queue Q = [(A, 0), (B, ∞), (C, ∞)]
Step 1: Extract min node 'A' (dist=0).
Relax neighbors of A:
- Neighbor B: new_dist = 0 + 5 = 5. update dist[B] = 5
- Neighbor C: new_dist = 0 + 2 = 2. update dist[C] = 2
Q is now: [(C, 2), (B, 5)]
Step 2: Extract min node 'C' (dist=2).
Node C is now locked. Relax neighbors of C:
- Neighbor B: new_dist = dist[C] + weight(C,B) = 2 + 1 = 3.
- Since 3 < 5, update dist[B] = 3.
Q is now: [(B, 3)]
Step 3: Extract min node 'B' (dist=3). Node B is locked.
Final Shortest Paths from A: {A: 0, B: 3, C: 2}
Plaintext
BellmanFord(Graph, source):
Initialize distance array dist[] to infinity for all nodes
dist[source] = 0
// Loop V-1 times
for i from 1 to |V| - 1:
for each edge (u, v) in Graph:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
// V-th pass to check for negative cycles
for each edge (u, v) in Graph:
if dist[u] + weight(u, v) < dist[v]:
throw Error("Graph contains a negative weight cycle")
return dist
Consider a graph with source \(A\):
Plaintext
Initialization:
dist = {A: 0, B: ∞, C: ∞}
Pass 1: Relax all edges (Order of edge processing can be random)
- Inspect (A, B): dist[A] + 4 = 4 < dist[B] (∞) -> dist[B] = 4
- Inspect (A, C): dist[A] + 3 = 3 < dist[C] (∞) -> dist[C] = 3
- Inspect (B, C): dist[B] + (-2) = 4 - 2 = 2 < dist[C] (3) -> dist[C] = 2
End of Pass 1: dist = {A: 0, B: 4, C: 2}
Pass 2: Relax all edges again
- Inspect (A, B): 0 + 4 = 4 (no change)
- Inspect (A, C): 0 + 3 = 3 (no change, 3 > 2)
- Inspect (B, C): 4 + (-2) = 2 (no change)
End of Pass 2: dist = {A: 0, B: 4, C: 2}
Pass 3 (Negative Cycle Check):
- Check all edges one last time. No values decrease.
Conclusion: No negative cycles present.
Final Shortest Paths from A: {A: 0, B: 4, C: 2}
| Metric | Dijkstra’s Algorithm | Bellman–Ford Algorithm |
|---|---|---|
| Core Strategy | Greedy Search | Dynamic Programming (Brute-Force Relaxation) |
| Time Complexity | \(O((V + E) \log V)\) (with Min-Heap) | \(O(V \cdot E)\) |
| Negative Weights | Fails | Handles successfully |
| Negative Cycles | Cannot detect | Detects explicitly on the \(V\)-th pass |
| Best Used For | General routing, fast execution on positive graphs | Graphs with negative traits, financial arbitrage detection |