Shortest paths and spanning trees
When edges have weights, shortest paths need smarter algorithms than BFS. Related problems ask for the cheapest way to connect every vertex.
Weighted shortest paths
The single-source shortest-path problem finds the minimum-weight path from a source to every vertex. Algorithms maintain a tentative distance for each vertex and relax edges: if dist[u] + w(u, v) < dist[v], update dist[v] and record u as v's predecessor. Algorithms differ in which edges they relax and in what order.
Dijkstra's algorithm
Dijkstra's algorithm, published in 1959, works when all weights are non-negative. It repeatedly takes the unfinished vertex with the smallest tentative distance from a priority queue, finalises it, and relaxes its outgoing edges. With a binary heap it runs in O((n + m) log n). It powers route planning, network routing protocols such as OSPF, and much more.
Why negative weights break Dijkstra
Dijkstra assumes that once a vertex has the smallest tentative distance, no later path can improve it, because extending a path never makes it cheaper. A negative edge discovered later could make a finalised distance wrong. Negative weights arise in practice, for example in currency-exchange or profit models.
Bellman-Ford
The Bellman-Ford algorithm relaxes every edge n - 1 times, enough for any shortest path, which has at most n - 1 edges. It handles negative weights and runs in O(nm). A further pass that still improves some distance proves the graph has a negative cycle reachable from the source, in which case shortest paths are undefined, since going around the cycle keeps lowering the cost.
All pairs and heuristics
Floyd-Warshall computes shortest paths between all pairs using dynamic programming in O(n^3) time, practical for a few hundred vertices. For a single destination on a map, A* search guides Dijkstra with a heuristic estimate of remaining distance, such as straight-line distance, often exploring far fewer vertices while still finding optimal paths if the estimate never overestimates.
Minimum spanning trees
A spanning tree of a connected undirected graph connects all vertices with n - 1 edges and no cycles. A minimum spanning tree (MST) has the smallest total weight, the cheapest way to connect cities by cable or houses by pipes. The cut property justifies greedy algorithms: the lightest edge crossing any division of the vertices into two groups belongs to some MST.
Kruskal's and Prim's algorithms
Kruskal's algorithm sorts edges by weight and adds each edge unless it would create a cycle, checked with a union-find (disjoint-set) structure; it runs in O(m log m). Prim's algorithm grows one tree from a start vertex, always adding the cheapest edge leaving the tree, using a priority queue, in O(m log n). Both are greedy and both are optimal for MSTs.
Worked example
Dijkstra from A with edges A-B 4, A-C 1, C-B 2, B-D 1, C-D 5. Start: A 0, others infinite. Finalise A; relax: B 4, C 1. Finalise C (1); relax: B min(4, 1 + 2) = 3, D 1 + 5 = 6. Finalise B (3); relax: D min(6, 3 + 1) = 4. Finalise D (4). Shortest A-to-D path is A, C, B, D with length 4, not the direct-looking A, C, D at 6.
Key takeaways
Shortest-path algorithms relax edges, improving tentative distances. Dijkstra's (1959) uses a priority queue for non-negative weights in O((n + m) log n). Negative edges break Dijkstra; Bellman-Ford handles them in O(nm) and detects negative cycles. Floyd-Warshall solves all pairs in O(n^3); A* uses admissible heuristics to speed single-target searches. Minimum spanning trees connect all vertices at least total weight; the cut property justifies greedy choices. Kruskal's uses sorted edges and union-find; Prim's grows a tree with a priority queue.
Flashcard
Improve dist[v] via edge (u, v) if shorter
Check your understanding
A graph of currency exchanges includes some negative edge weights. Which algorithm can find shortest paths and detect negative cycles?