Algorithms · Lesson 12 of 17
Shortest Paths: Dijkstra and Bellman-Ford
Learn Dijkstra's algorithm and Bellman-Ford in Python to find shortest paths in weighted graphs, handle negative edges and detect negative cycles.
- Advanced
- 20 min read
- 4 objectives
Before this lessonLesson 11: Graph Traversal: BFS and DFS
What you will learn
- Explain why BFS fails on weighted graphs
- Implement Dijkstra with a heap and rebuild the path
- Implement Bellman-Ford and detect negative cycles
- Choose the right algorithm and state its complexity
Your Progress
0 of 17 lessons 0%
- Lessons0 / 17
- Completed0
- Est. time left~ 5 hours
Create a free account to keep your progress on every device.
Tip: pressing Next marks this lesson complete automatically.
BFS finds the path with the fewest edges. But real graphs have weights: road distances, network latency, ticket prices. A route with three short roads can beat one long highway, and BFS cannot see that. This lesson covers the two shortest-path algorithms every developer should know: Dijkstra, the fast default for non-negative weights, and Bellman-Ford, the slower but more general one that handles negative weights.
Both are built on one operation called relaxation. Keep a best-known distance dist[v] for every node, starting at infinity. When you look at an edge u to v with weight w, ask: is going through u better? If dist[u] + w < dist[v], update dist[v]. The algorithms differ only in the order they relax edges.
Why BFS is not enough
# delivery times in minutes between stackcone warehouses
roads = {
"A": [("B", 10), ("C", 3)],
"B": [("D", 2)],
"C": [("B", 4), ("D", 8), ("E", 2)],
"D": [("E", 7)],
"E": [],
}
# BFS would pick A -> B -> D (2 edges, 12 minutes)
# but A -> C -> B -> D is 3 edges and only 9 minutes
print(10 + 2, 3 + 4 + 2)12 9
Dijkstra's algorithm
Dijkstra is BFS with a priority queue instead of a plain queue. It always expands the unfinished node with the smallest known distance. With non-negative weights, that node's distance can never improve later (any other route would go through a node that is already at least as far), so it is final.
# from earlier in this lesson
# delivery times in minutes between stackcone warehouses
roads = {
"A": [("B", 10), ("C", 3)],
"B": [("D", 2)],
"C": [("B", 4), ("D", 8), ("E", 2)],
"D": [("E", 7)],
"E": [],
}
# BFS would pick A -> B -> D (2 edges, 12 minutes)
# but A -> C -> B -> D is 3 edges and only 9 minutes
# new code
import heapq
def dijkstra(graph, source):
dist = {node: float("inf") for node in graph}
parent = {source: None}
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry, already found better
for v, w in graph[u]:
if d + w < dist[v]: # relax
dist[v] = d + w
parent[v] = u
heapq.heappush(heap, (dist[v], v))
return dist, parent
def path_to(parent, target):
path = []
while target is not None:
path.append(target)
target = parent[target]
return path[::-1]
dist, parent = dijkstra(roads, "A")
print(dist)
print(path_to(parent, "D"), dist["D"]){'A': 0, 'B': 7, 'C': 3, 'D': 9, 'E': 5}
['A', 'C', 'B', 'D'] 9Python's heapq has no "decrease key" operation, so instead of updating an entry we push a new one and skip stale entries when popped (the d > dist[u] check). This "lazy deletion" is the standard Python approach.
Time O((V + E) log V): each edge can push one heap entry, and each push or pop costs O(log V). Space O(V + E). This is fast enough for graphs with millions of edges, and it is the core of real routing engines (which add tricks like A* heuristics and precomputed shortcuts).
You can see it with the textbook version of Dijkstra, which marks each node as finished the moment it is popped and never touches it again:
import heapq
def dijkstra_textbook(graph, source):
dist = {node: float("inf") for node in graph}
dist[source] = 0
done = set()
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if u in done:
continue
done.add(u) # u is now final
for v, w in graph[u]:
if v not in done and d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist
tricky = {"S": [("A", 2), ("B", 5)], "A": [("C", 1)], "B": [("A", -4)], "C": []}
print(dijkstra_textbook(tricky, "S"))
print("true answer: A = 1, C = 2 (S -> B -> A -> C = 5 - 4 + 1)"){'S': 0, 'A': 2, 'B': 5, 'C': 3}
true answer: A = 1, C = 2 (S -> B -> A -> C = 5 - 4 + 1)Dijkstra finalised A at distance 2 and C at 3 before it discovered the cheaper route through B. (The lazy version above sometimes recovers by re-pushing nodes, but that can take exponential time and is not something to rely on.)
Bellman-Ford
Bellman-Ford is beautifully simple: relax every edge, and repeat that V - 1 times. Why V - 1? A shortest path without cycles has at most V - 1 edges, and after round k, every path with k edges has been fully relaxed. It does not care about the order, so negative weights are fine.
# from earlier in this lesson
# delivery times in minutes between stackcone warehouses
roads = {
"A": [("B", 10), ("C", 3)],
"B": [("D", 2)],
"C": [("B", 4), ("D", 8), ("E", 2)],
"D": [("E", 7)],
"E": [],
}
# BFS would pick A -> B -> D (2 edges, 12 minutes)
# but A -> C -> B -> D is 3 edges and only 9 minutes
tricky = {"S": [("A", 2), ("B", 5)], "A": [("C", 1)], "B": [("A", -4)], "C": []}
# new code
def bellman_ford(graph, source):
edges = [(u, v, w) for u in graph for v, w in graph[u]]
dist = {node: float("inf") for node in graph}
dist[source] = 0
for _ in range(len(graph) - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
break # early exit: nothing improved
# one more pass: any improvement means a negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("negative cycle reachable from source")
return dist
print(bellman_ford(tricky, "S"))
print(bellman_ford(roads, "A")){'S': 0, 'A': 1, 'B': 5, 'C': 2}
{'A': 0, 'B': 7, 'C': 3, 'D': 9, 'E': 5}Time O(V * E), space O(V + E). Much slower than Dijkstra on big graphs, which is why you only reach for it when weights can be negative.
Detecting negative cycles
If a cycle has a negative total, you can loop around it forever and the "shortest" path is minus infinity. Bellman-Ford detects this with one extra pass: if anything still improves after V - 1 rounds, there must be a negative cycle. A real use is currency arbitrage: take edge weights as -log(rate), and a negative cycle is a sequence of trades that ends with more money than it started.
# from earlier in this lesson
def bellman_ford(graph, source):
edges = [(u, v, w) for u in graph for v, w in graph[u]]
dist = {node: float("inf") for node in graph}
dist[source] = 0
for _ in range(len(graph) - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
break # early exit: nothing improved
# one more pass: any improvement means a negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("negative cycle reachable from source")
return dist
# new code
loop = {"X": [("Y", 1)], "Y": [("Z", -3)], "Z": [("X", 1)]}
try:
bellman_ford(loop, "X")
except ValueError as e:
print("error:", e)error: negative cycle reachable from source
Choosing an algorithm
- All edges equal weight: BFS, O(V + E).
- Non-negative weights, one source: Dijkstra, O((V + E) log V).
- Negative weights or you need negative-cycle detection: Bellman-Ford, O(V * E).
- Edges of weight 0 or 1 only: 0-1 BFS with a deque, O(V + E).
- All pairs on a small graph (a few hundred nodes): Floyd-Warshall, O(V3).
Recap
- Weighted shortest paths are built on relaxation: improve
dist[v]if going through u is cheaper. - Dijkstra always expands the closest unfinished node using a heap, and requires non-negative weights.
- In Python, push duplicates onto the heap and skip stale entries instead of decreasing keys.
- Bellman-Ford relaxes all edges V - 1 times and handles negative weights.
- An extra Bellman-Ford pass that still improves something proves a negative cycle.
# Write your solution here
Finished reading? Mark this lesson complete to track your progress.