Shortest Paths, Minimum Spanning Trees and Union-Find

Weighted graphs support two optimization problems that sound similar but have different goals. A shortest-path problem minimizes the weight along a route between vertices. A minimum spanning tree minimizes the total weight of edges used to connect every vertex. A shortest-path tree is rooted at a chosen source; a minimum spanning tree has no source and need not give shortest routes from any vertex.

Paths and Distance

The weight of a path is the sum of its edge weights. A single-source shortest-path problem asks for minimum distances from one source to every reachable vertex. An all-pairs problem asks for every ordered source-destination pair. Unreachable distances are represented by infinity rather than by an ordinary finite value that might also be a legitimate cost.

Shortest paths have optimal substructure: every subpath of a shortest path is itself shortest between its endpoints, assuming a finite optimum exists. Most algorithms repeatedly use relaxation. For an edge (u, v) of weight w, test whether

distance[u] + w < distance[v]

If so, assign the smaller value and record u as the predecessor of v. The infinity case and numeric overflow must be handled before performing the addition.

Predecessor links reconstruct paths. Starting at a reachable destination, follow predecessors to the source and reverse the sequence. Distances alone state costs but do not reveal the chosen route.

Dijkstra’s Algorithm

Dijkstra’s algorithm solves single-source shortest paths when every edge weight is nonnegative. Initialize the source distance to zero and all others to infinity. Repeatedly select an unsettled vertex with minimum tentative distance, settle it and relax all outgoing edges.

The key correctness fact is that the selected minimum can no longer be improved. Any alternative route reaching it through an unsettled vertex would first have to reach a vertex whose tentative distance is at least as large and adding nonnegative edges cannot reduce the cost. This argument fails with a negative edge: a vertex considered final may later receive a cheaper route through a negative step.

With an adjacency matrix and a linear scan to choose each minimum, Dijkstra takes O(V²) time and can be appropriate for dense graphs. With adjacency lists and a binary min-heap, it commonly takes O((V + E) log V), often written O(E log V) for a connected graph.

Many standard priority queues lack a direct decrease-key operation. A practical implementation can insert a new (distance, vertex) pair whenever a distance improves. When a pair is removed, discard it if its stored distance differs from the current best distance. These stale entries preserve correctness at the cost of additional heap items.

Zero-weight edges are allowed. Negative edges are not, even when there is no negative cycle. For graphs with negative edges, Bellman–Ford is a standard alternative: it relaxes every edge repeatedly, detects reachable negative cycles and costs O(VE).

Floyd–Warshall Algorithm

Floyd–Warshall computes all-pairs shortest paths with dynamic programming. Begin with a matrix dist in which dist[i][i] = 0, direct edges hold their weights and missing edges hold infinity. For each vertex k, update every pair (i, j):

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

After iteration k, the invariant is that dist[i][j] is the shortest path whose internal vertices come only from the processed set through k. The update chooses between avoiding k and passing through k.

Three nested vertex loops give Theta(V³) time and the distance matrix uses Theta(V²) space. Loop order matters: k must be outermost so each stage builds on paths using only already admitted intermediate vertices.

Floyd–Warshall permits negative edges but assumes shortest distances are well-defined. After completion, dist[v][v] < 0 indicates a negative cycle reachable in the relevant path relation. Repeated traversal of such a cycle can reduce cost without bound. A next-hop or predecessor matrix can be updated alongside distances to reconstruct actual paths.

Spanning Trees

For a connected undirected graph, a spanning tree includes every vertex, remains connected and contains no cycle. Every spanning tree on V vertices has exactly V - 1 edges. Removing any tree edge disconnects it and adding any non-tree edge creates exactly one cycle.

A minimum spanning tree or MST, is a spanning tree with minimum total edge weight. An MST may not be unique when equal-weight choices exist, although the minimum total weight is fixed. Distinct edge weights guarantee a unique MST. Negative edge weights cause no difficulty; if a negative edge can be included without violating the tree structure, it is attractive rather than invalid.

For a disconnected undirected graph, no single spanning tree exists. Applying an MST method to each component produces a minimum spanning forest.

Two properties justify greedy MST algorithms. The cut property says that a lightest edge crossing a cut is safe for some MST, subject to standard tie wording. The cycle property says that a uniquely heaviest edge on a cycle cannot belong to an MST. Prim’s and Kruskal’s algorithms exploit these principles differently.

Prim’s Algorithm

Prim’s algorithm grows one connected tree. Start from any vertex. At each step, choose a minimum-weight edge crossing from a vertex already in the tree to a vertex outside it and add the new vertex and edge.

An efficient implementation keeps, for each outside vertex, the cheapest known edge connecting it to the growing tree. A min-priority queue selects the smallest such key. When an edge from a newly added vertex offers a cheaper connection, update the key and parent.

With adjacency lists and a binary heap, time is O(E log V). With a matrix and linear key selection, it is O(V²). The starting vertex can change the chosen tree when ties exist, but not the minimum total weight.

If the graph is disconnected, the heap eventually has no finite crossing edge for remaining vertices. The implementation should report disconnection or deliberately restart to produce a forest.

Kruskal’s Algorithm

Kruskal’s algorithm begins with every vertex as a separate component and processes edges in nondecreasing weight order. It adds an edge exactly when its endpoints currently belong to different components. Such an edge connects two trees and cannot create a cycle. Once V - 1 edges have been accepted in a connected graph, the spanning tree is complete.

Sorting edges costs O(E log E). Component tests and merges are performed by a disjoint-set union structure. Because E is at most on the order of V² in a simple graph, the sorting bound is often related to O(E log V). Kruskal is particularly convenient when the graph already exists as an edge list.

Self-loops are never useful because their endpoints are already the same component. Parallel edges are allowed; ordering naturally considers the lighter candidates first.

Disjoint-Set Union

A disjoint-set union structure, also called union–find, maintains a partition of elements into nonoverlapping sets. It supports:

• makeSet(x), which creates a singleton set;
• find(x), which returns a representative of x’s set;
• union(a, b), which merges two sets when their representatives differ.

A forest representation gives every element a parent. A representative is a root whose parent is itself. A naive sequence of unions can create a tall chain. Union by rank or union by size attaches the shallower or smaller root beneath the other. Path compression makes nodes visited during find point closer or directly to the representative.

Together, these optimizations give almost constant amortized time per operation, formally O(alpha(n)), where the inverse Ackermann function grows extraordinarily slowly. The structure supports merging and connectivity testing, but it does not efficiently split a set after an edge is removed.

In Kruskal’s algorithm, find(u) == find(v) means the endpoints already have a path through accepted edges, so adding (u, v) would create a cycle. Otherwise, accept the edge and union the components.

Comparing the Algorithms

BFS is the appropriate shortest-path algorithm when every edge has equal unit cost. Dijkstra handles arbitrary nonnegative weights from one source. Bellman–Ford accommodates negative edges and detects reachable negative cycles. Floyd–Warshall provides all-pairs results and is especially direct for dense graphs of moderate vertex count.

Prim and Kruskal solve total network connection rather than route distance. Prim grows outward from a connected set and fits adjacency representations. Kruskal considers a globally ordered edge stream and joins components. Both can produce different but equally weighted MSTs when ties occur.

Consider a triangle whose source-to-middle edge weighs 2, middle-to-end weighs 2 and source-to-end weighs 3. The MST chooses weights 2 and 2, total 4, because those connect all vertices cheaply. The shortest path from source to end is the direct edge of weight 3, not the two-edge route of weight 4. This demonstrates why an MST is not a shortest-path tree.

Correctness and Testing

Shortest-path code should test an unreachable vertex, zero-weight edges, alternative equal-cost paths, large weights near numeric limits and any forbidden negative edge. Path reconstruction must terminate at the source and agree with the reported distance.

MST tests should verify that the result has V - 1 edges for a connected graph, is acyclic, reaches every vertex and has the expected total weight. Include equal weights, negative weights, parallel edges and disconnected input. Union–find tests should merge sets in adversarial orders and confirm that repeated finds preserve component membership.

These algorithms are reliable when their preconditions are explicit. Nonnegative weights justify Dijkstra’s finalization, undirected connectivity defines an MST and union–find preserves the component partition that makes Kruskal’s cycle decisions correct.