Shortest Path Algorithms

Module 4.9 — Dijkstra & Bellman-Ford with edge relaxation

Graph:
Algorithm:
Speed:
Step 0 / 0
42518216A∞B∞C∞D∞E∞F∞

Distance Table

A
∞
B
∞
C
∞
D
∞
E
∞
F
∞

Algorithm Comparison

Dijkstra
O((V+E) log V)
Greedy + PQ
No negative edges
Bellman-Ford
O(V * E)
V-1 iterations
Handles negatives

Edge Relaxation

if dist[u] + w(u,v) < dist[v]:
  dist[v] = dist[u] + w(u,v)

If going through u gives a shorter path to v, update the distance.