Reading Shortest Paths From a Minimum Spanning Tree

A minimum spanning tree gives the cheapest way to connect every vertex, not the cheapest way to travel between two of them, and reading routes off it gives paths that can be longer than they need to be. This card shows the difference on the topic's graph and says which algorithm answers each question.

The symptom is a route that is valid but too long. A planner that sends traffic along the minimum spanning tree of the topic's graph routes A to F through A, C, B, D and E, at a cost of 17. Dijkstra's algorithm on the whole graph finds A, C, B, D, F at 15. The trigger is treating the tree as a map of best routes, which is easy to do because it does connect everything, and cheaply.

The mechanism is that the two trees minimise different things. A minimum spanning tree minimises the sum of its edges, counted once each. A shortest-path tree from A, the tree of parents Dijkstra's algorithm builds, minimises each vertex's distance from A, where an edge near A is counted again in every route that passes through it. D-F 7 is left out of the minimum spanning tree because E-F 6 already connects F more cheaply in total. For a trip from A it is the better edge, since it skips the detour through E. C-E 9 is left out for the same reason, and costs E one unit.

The run also built Dijkstra's tree from A: A-C, B-C, B-D, C-E and D-F, which adds up to 24, against 17 for the minimum spanning tree. Each tree is the best at its own job and worse at the other's: no single tree is both, here or in general.

The cost of the mistake is every route through the network running longer than it could, which is invisible on any one trip, because each still arrives. The remedy is to pick the algorithm by the question. To build a network that connects every site for the least total, find a minimum spanning tree. To get from one place to others as cheaply as possible, run Dijkstra's algorithm from that place, as in Dijkstra's Algorithm: Settling the Closest Vertex Next.