Weighted Graphs, Dijkstra and Union–Find

Choose an algorithm from the edge weights

The right shortest-path algorithm depends on what one edge can cost:

Dijkstra fails with negative weights because a vertex considered final may later receive a cheaper path through a negative edge.

Dijkstra's algorithm

Maintain dist[v], the best source-to-v distance found so far, and a min-priority queue of (distance, vertex) candidates.

1. Set the source distance to 0 and every other distance to infinity.
2. Pop the smallest candidate.
3. If it is stale—larger than the current dist—skip it.
4. For every edge u → v of weight w, relax it: if dist[u] + w < dist[v], update v and push the new candidate.

With non-negative weights, once the smallest current candidate is popped, no path through a farther unsettled vertex can make it smaller.

Shortest paths and spanning trees are different

A shortest-path tree minimises distance from one chosen source to every vertex. A minimum spanning tree (MST) connects every vertex with the minimum total edge cost. An MST does not necessarily give the shortest route from a particular source.

Two standard MST algorithms are:

• Kruskal: sort edges by cost and accept an edge when it joins two different components.
• Prim: grow one connected tree, repeatedly taking the cheapest edge leaving it.

Kruskal needs a fast way to ask whether two vertices already belong to the same component. That is the job of union–find.

Union–find (disjoint-set union)

Union–find stores a forest of parent pointers and supports:

• find(x): return the representative root of x's component,
• union(a, b): merge the components if their roots differ.

Two optimisations make a sequence of operations almost linear:

• Path compression: during find, point visited nodes closer to the root.
• Union by size or rank: attach the smaller tree below the larger root.

The amortised cost per operation is O(α(n)), where α grows so slowly that it is below 5 for practical inputs.

Union–find handles undirected connectivity, redundant-edge detection, Kruskal's algorithm, account merging and offline grouping. It does not directly answer directed reachability or shortest paths.

Kruskal implementation

The program returns the minimum spanning-tree cost, or −1 if the graph is disconnected.

def mst_cost(n, edges):
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while x != parent[x]:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = used = 0
    for cost, u, v in sorted(edges):
        a, b = find(u), find(v)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        total += cost
        used += 1
    return total if used == n - 1 else -1


edges = [(1, 0, 1), (4, 0, 2), (2, 1, 2), (5, 1, 3), (3, 2, 3)]
print("mst cost:", mst_cost(4, edges))

mst cost: 6

A graph-algorithm checklist

Before coding, ask whether edges are directed, whether weights can be negative, whether the goal is reachability, shortest paths or total connection cost, and whether the graph can be disconnected. Those answers usually select the algorithm.

Practice non-negative shortest paths in Shortest Paths with Dijkstra and component merging in Minimum Cost to Connect a Graph. The earlier Graphs, BFS and DFS guide covers unweighted traversal and connected components.