Lessons 12–16 covered unweighted graphs, where BFS gives the shortest path because every edge is one step. Real problems put weights on edges — distances, costs, times — and BFS no longer works. This lesson covers the four weighted-graph algorithms that senior interviews lean on, and, just as importantly, how to pick the right one in ten seconds.
The idea
Build the same adjacency list as before, but each neighbour now carries a weight: {u: [(v, w), ...]}. Then choose:
- Dijkstra — single-source shortest path, non-negative weights. O(E log V).
- Bellman-Ford — single-source with negative weights, or negative-cycle detection. O(VE).
- Floyd-Warshall — all-pairs shortest paths, small graphs. O(V³).
- Prim / Kruskal — minimum spanning tree: the cheapest set of edges that keeps everything connected.
Dijkstra: a heap-based BFS
Dijkstra is just BFS that always expands the cheapest unfinalised node instead of the nearest-by-steps. A min-heap keyed by distance-so-far does exactly that. The first time you pop a node, that distance is final:
import heapq
from collections import defaultdict
def dijkstra(n, edges, src):
adj = defaultdict(list)
for u, v, w in edges:
adj[u].append((v, w))
dist = {}
heap = [(0, src)] # (distance so far, node)
while heap:
d, u = heapq.heappop(heap)
if u in dist: # already finalised → skip
continue
dist[u] = d
for v, w in adj[u]:
if v not in dist:
heapq.heappush(heap, (d + w, v))
return dist
# dijkstra(4, [[0,1,1],[0,2,4],[1,2,2],[2,3,1]], 0) -> {0:0, 1:1, 2:3, 3:4}The if u in dist: continue is the key line — a node can be pushed many times with different tentative distances, but only the first (smallest) pop counts. This is the template behind “minimum time/cost to reach X” problems.
Bellman-Ford: when weights go negative
Dijkstra assumes that once a node is popped, no cheaper path can appear later — which is false if an edge can be negative. Bellman-Ford instead relaxes every edge V − 1 times. After that, all shortest paths are final; one more pass that still improves something proves a negative cycle:
def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1): # relax every edge V-1 times
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges: # one more pass → negative cycle?
if dist[u] + w < dist[v]:
return None # negative cycle reachable
return dist
# bellman_ford(3, [[0,1,4],[0,2,5],[1,2,-3]], 0) -> [0, 4, 1]A beautiful variant bounds the number of edges (“cheapest flight with at most K stops”): run exactly K + 1 relaxation rounds, each on a snapshot of the previous round so one round can’t use an edge twice.
Floyd-Warshall: all-pairs in three lines
When you need the shortest path between every pair of nodes and the graph is small (V ≤ ~400), Floyd-Warshall is the simplest thing that works. For each intermediate node k, ask whether routing i → k → j beats the current i → j:
def floyd_warshall(n, edges):
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w # undirected; drop one side if directed
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distThe triple loop is O(V³), but the constant factor is tiny and it handles negative edges (just not negative cycles). Keep the loop order k, i, j — k outermost is what makes it correct.
Minimum spanning tree: Prim
An MST is the cheapest subset of edges that connects every node (no cycles). Prim grows the tree one node at a time, always adding the cheapest edge that reaches a new node — Dijkstra’s cousin with a min-heap:
import heapq
def prim_mst(n, adj): # adj: {u: [(v, w), ...]}
visited = [False] * n
heap = [(0, 0)] # (edge weight, node)
total = 0; count = 0
while count < n:
w, u = heapq.heappop(heap)
if visited[u]:
continue
visited[u] = True; total += w; count += 1
for v, wt in adj[u]:
if not visited[v]:
heapq.heappush(heap, (wt, v))
return totalKruskal is the other MST algorithm: sort all edges by weight and add each one unless it would form a cycle, using union-find (Lesson 16) to test connectivity. Prim shines on dense graphs, Kruskal on sparse edge lists.
When to reach for which
- “Minimum time / cost to reach a target”, non-negative weights → Dijkstra.
- Weights can be negative, or “detect a negative cycle”, or “at most K edges” → Bellman-Ford.
- “Shortest path between every pair”, small graph → Floyd-Warshall.
- “Connect all points / cities for the minimum total cost” → MST (Prim / Kruskal).
- All edge weights are 0 or 1 → 0-1 BFS (a deque: push 0-weight edges to the front, 1-weight to the back) — faster than Dijkstra.
Pitfalls
- Dijkstra with negative edges. It gives wrong answers silently — a finalised node might still have a cheaper path through a negative edge. If any weight is negative, use Bellman-Ford.
- Forgetting the stale-entry skip. Without
if u in dist: continue(or a distance check), Dijkstra still works but reprocesses nodes and can blow up. Always skip finalised nodes. - Floyd-Warshall loop order.
kmust be the outermost loop. Any other order computes garbage. - MST vs shortest path. An MST minimises total edge weight, not the path between two specific nodes. Don’t reach for Prim when the question asks for a path.
Recap
Weighted graphs need weighted algorithms: Dijkstra (heap-based BFS, non-negative, O(E log V)), Bellman-Ford (relax V−1 times, handles negatives and the K-stops variant, O(VE)), Floyd-Warshall (all-pairs triple loop, O(V³)), and MST via Prim/Kruskal for the cheapest connecting tree. The tell is in the words: minimum cost/time to reach → Dijkstra; negative / at most K stops → Bellman-Ford; every pair → Floyd-Warshall; connect everything cheaply → MST.
Practice: 10 solved problems on advanced graphs → — cover each one, solve it yourself, then check the tested code.