Both find shortest paths from a source in a weighted graph. Dijkstra is faster but needs non-negative weights; Bellman-Ford is slower but handles negative edges and detects negative cycles.
Repeatedly expand the closest unvisited node and relax its neighbors.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
Relax all edges V-1 times; a further relaxation means a negative cycle.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Weights | non-negative | any (incl. negative) |
| Time | O((V+E) log V) | O(V·E) |
| Neg. cycle | n/a | detects it |
Use Dijkstra by default for non-negative weights (maps, networks). Use Bellman-Ford when negative edges exist (e.g., arbitrage). Dijkstra silently breaks on negative weights — a classic trap.
Shortest-path algorithms power routing, navigation, network protocols, and dependency cost analysis.
Knowing the non-negative-weight constraint on Dijkstra prevents wrong answers in the field.
The relaxation idea connects greedy and DP thinking, making it a rich senior-level topic.