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 the same, where one step is one step. This topic drops that assumption. Now every edge carries a weight, a cost to cross it. The question changes from "is there a path" to "what is the cheapest path".
Think of it as an upgrade to a road map, with tolls. Before, any road that connected two cities was as good as any other road, and the question was only whether a route existed. Now every road has a price. Two different questions become worth asking separately: what is the cheapest way from this one city to that one city (shortest path), and what is the cheapest way to connect every city to every other city, with no particular pair in mind (minimum spanning tree). These are 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 final: locked in, never revisited
visited = {}
minHeap = [(0, source)] // (distance, node). The Phase 5 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): // to add this edge would NOT create a cycle
uf.union(u, v)
mst.append((u, v, weight))
totalWeight += weight
return mst, totalWeightThe O((V+E) log V) of Dijkstra comes from a pop and push of each edge at most one time, and every heap operation on a heap sized around V costs O(log V), the same push/pop bound from Heaps & Priority Queue, paid one time per edge examined. The O(E log E) of Kruskal is dominated completely by the initial sort of all edges by weight. Once sorted, to process 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 almost free. (Bellman-Ford, mentioned above for negative weights, costs O(V×E): no heap, only V full passes over every edge, each pass relaxing distances a little further.)
| 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 new (distance, node) pair instead of an update of 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) | The sort of E edges dominates. The union-find pass after it 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) | This is V full passes over every edge, each pass able to improve a distance. It is the honest, slower fallback once negative weights are possible. |
Dijkstra with a negative edge weight
This does not crash or make an infinite loop. It can quietly produce a wrong answer, which is worse. The whole correctness argument of Dijkstra rests on "the closest not-yet-final node is done, and nothing can beat it later". That argument holds only because every alternative path can only get longer as it crosses more edges. A negative edge breaks this. 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 had not looked at yet, because that edge was 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 full confidence.
Not skipping stale heap entries
A plain heap has no decrease-key operation. You cannot reach into the middle of it and update the priority of one entry. So instead, every time a shorter distance to a node is found, a new (distance, node) pair is pushed, and the old, larger entry stays in the heap. To pop that stale entry later and process it as if it were new work is wasted at best. If you skip the visited check that catches it (if node in visited: continue), the algorithm can relax edges from a node again with an already-beaten, larger distance, which corrupts the results downstream.
Kruskal without the union-find cycle check
If you skip the check, the algorithm builds whatever the sorted edge list gives it, cheapest first, until it runs out of edges or reaches some other stop 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. A spanning tree by definition cannot have a cycle. The union-find check is not an optimization here. It is the one thing that makes the output an actual tree instead of only "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 completely. Minimum spanning tree (Kruskal) optimizes the total cost of a structure that touches every node at least one time, 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 usually not 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 asked before you pick the algorithm.
Sign in to mark problems done — progress syncs across devices.