Minimum Spanning Tree¶

Definition¶

Given a connected undirected network with nonnegative edge lengths, a minimum spanning tree is a spanning tree whose total selected edge length is smallest among all spanning trees of that network.

Interpretation¶

The objective is to connect every location at minimum total construction length, for example the cheapest set of roads or cables that links all sites. It does not minimize the travel distance from one selected origin.

A weighted network from A to F with the edges of a minimum spanning tree of total length 13 highlighted.

The five green edges reach all six vertices without a cycle and have total length $1+2+2+3+5=13$ $13$ ; no other spanning tree of this network is shorter. Each grey edge is the longest edge on a cycle whose other edges are green: $A-B$ (4) closes $A-B-C-A$ with edges of length 1 and 2, and $C-D$ (8), $C-E$ (10) and $D-F$ (6) close cycles in the same way. Such an edge is never needed: the rest of its cycle already connects its endpoints more cheaply.

Simple rules solve the problem exactly: the Kruskal method accepts the shortest edges that close no cycle, and the Dijkstra-Prim method grows one tree from a start vertex. For many optimization problems, always taking the cheapest next step is only a heuristic; here it is guaranteed to be optimal.

A minimum spanning tree is not a collection of shortest paths. In a triangle with edges $A-B$ and $B-C$ of length 2 and $A-C$ of length 3, the minimum spanning tree uses the two edges of length 2, so $A$ and $C$ are $4$ apart in the tree, although the shortest path between them is the direct edge of length 3.

Key Results¶

Both Dijkstra-Prim and Kruskal methods produce a minimum spanning tree.
There may be several minimum trees with the same total length.
Tie choices may be explored to identify alternative minimum trees.

Examples¶

The green edges in the figure have total length $1+2+2+3+5=13$ $13$ . They form a minimum spanning tree.

Roads can be selected to connect all cities while minimizing total road length.
Week 4 practice 1 has two minimum spanning trees, differing by the choice B-F or F-G.

Prerequisites¶

Spanning Tree

Sources¶

OR Modelling · Week 4

Aliases: MST, minimal spanning tree, minimum-weight spanning tree, shortest spanning tree

Last updated: 20 October 2026 03:02