Advanced Graph Algorithms
Quick reference
| Dijkstra's algorithm | O((V+E) log V) |
| Kruskal's algorithm | O(E log E) |
| Bellman-Ford (mentioned, not built above) | O(V Γ E) |
Graph Fundamentals answered one question: can I get there at all. DFS and BFS walk edges as if every road were identical β one step is one step. This topic drops that assumption. Now every edge carries a weight, a cost to cross it, and the question changes from "is there a path" to "what's the cheapest path."
Think of it as upgrading a road map with tolls. Before, any road connecting two cities was as good as any other, and the question was just whether a route existed. Now every road has a price tag, and two different questions become worth asking separately: what's the cheapest way from this one city to that one city (shortest path), and what's the cheapest way to connect every city to every other city at all, with no particular pair in mind (minimum spanning tree). Different questions, and β as Break It shows β different algorithms.
The weighted graph
structure WeightedGraph (adjacency list):
adj: map from node -> list of (neighbor, weight) pairsDijkstra's algorithm β single-source shortest path, non-negative weights β O((V+E) log V)
function dijkstra(source, adj):
dist = map, dist[source] = 0, every other node = infinity
// nodes whose shortest distance is finalized β locked in, never revisited
visited = {}
minHeap = [(0, source)] // (distance, node) β Phase 5's heap, ordered by distance
while minHeap is not empty:
(d, node) = pop minimum from minHeap
if node in visited:
continue // a stale, already-beaten entry β skip it (see Break It)
visited.add(node)
for (neighbor, weight) in adj[node]:
newDist = d + weight
if newDist < dist[neighbor]:
dist[neighbor] = newDist
push (newDist, neighbor) onto minHeap
return distKruskal's algorithm β minimum spanning tree β O(E log E)
function kruskal(nodes, edges): // each edge is (u, v, weight)
sort edges by weight ascending
uf = UnionFind(nodes) // Phase 6: every node starts as its own group
mst = []
totalWeight = 0
for (u, v, weight) in edges:
if uf.find(u) != uf.find(v): // adding this edge would NOT create a cycle
uf.union(u, v)
mst.append((u, v, weight))
totalWeight += weight
return mst, totalWeightDijkstra's O((V+E) log V) comes from popping and pushing each edge at most once, and every heap operation on a heap sized around V costs O(log V) β the same push/pop bound from Heaps & Priority Queue, just paid once per edge examined. Kruskal's O(E log E) is dominated entirely by the initial sort of all edges by weight; once sorted, processing each edge costs a find and at most one union, both near-O(1) thanks to path compression and union by rank β the sort is the expensive part, everything after it is nearly free. (Bellman-Ford, mentioned above for negative weights, costs O(VΓE) β no heap, just V full passes over every edge, relaxing distances a little further each pass.)
| Operation | Time | Space | Why |
|---|---|---|---|
| Dijkstra's algorithm | O((V+E) log V) | O(V + E) | Without a decrease-key operation, every shorter distance found pushes a brand-new (distance, node) pair instead of updating one in place (see Break It) β so the heap can hold up to one stale entry per edge relaxation, O(E), on top of the O(V) dist map. |
| Kruskal's algorithm | O(E log E) | O(V + E) | Sorting E edges dominates; the union-find pass afterward is O(E Β· Ξ±(V)) β O(E), which is smaller than the sort and disappears into its bound. |
| Bellman-Ford (mentioned, not built above) | O(V Γ E) | O(V) | V full passes over every edge, each pass potentially improving a distance β the honest, slower fallback once negative weights are possible. |
Dijkstra with a negative edge weight
This doesn't crash or infinite-loop β it can silently produce a wrong answer, which is worse. Dijkstra's entire correctness argument rests on "the closest not-yet-finalized node is done β nothing can beat it later," and that argument only holds because every alternative path can only get longer as it crosses more edges. A negative edge breaks that: a node finalized early with distance 10 might have had a truly-shorter path of length 8 through an edge of weight -5 that Dijkstra hadn't looked at yet, because that edge lived behind a node that looked farther away at the time. Once a node is popped as visited, Dijkstra never revisits it β so that better path is never found, and the algorithm reports 10 with total confidence.
Not skipping stale heap entries
A plain heap has no decrease-key operation β you can't reach into the middle of it and update one entry's priority. So instead, every time a shorter distance to a node is found, a brand-new (distance, node) pair gets pushed, leaving the old, larger entry still sitting in the heap. Popping that stale entry later and processing it as if it were new work is wasted at best; skipping the visited check that catches it (if node in visited: continue) means the algorithm can re-relax edges from a node using an already-beaten, larger distance, corrupting results downstream.
Kruskal without the union-find cycle check
Skip the check and the algorithm just builds whatever the sorted edge list hands it, cheapest first, until it runs out of edges or hits some other stopping point β nothing stops it from adding an edge that reconnects two nodes already in the same group. The result is a cyclic subgraph, not a tree at all, and a spanning tree by definition cannot have a cycle. The union-find check isn't an optimization here β it's the one thing that makes the output an actual tree instead of just "a cheap subset of edges."
"Shortest path" and "minimum spanning tree" are different problems
Shortest path (Dijkstra) optimizes the total cost of one specific route between two chosen nodes β other nodes in the graph may be ignored entirely. Minimum spanning tree (Kruskal) optimizes the total cost of a structure that touches every node at least once, with no particular pair of endpoints in mind. They can even disagree on the same graph: the cheapest way to connect every city (MST) is not generally the cheapest way to get from city A to city B specifically β the MST might route that trip the long way around if it saves money elsewhere. Name which question is actually being asked before picking the algorithm.
Sign in to mark problems done β progress syncs across devices.