Why doesn't a minimum spanning tree give the cheapest route between two given nodes?
answer
- One global sum, or many pairwise distances?
- What exactly does 'minimum' attach to?
- Try a three-node triangle with weights
- MST may omit a cheap direct edge
- Tree path minimizes heaviest edge, not total
basics
~20 sA minimum spanning tree minimizes one global sum: the total weight of the edges keeping every node connected. It promises nothing about any specific pair, so its path between two nodes can cost more than a direct link.
solid answer
~40 sThe two structures optimize different things. A minimum spanning tree (MST) minimizes one number: the sum of the weights of the `V-1` edges that keep all `V` nodes connected. A shortest-path tree minimizes a different quantity — the distance from one chosen source to every other node, separately. Take three offices with trench costs A-B = 3, A-C = 2, B-C = 2. The MST takes the two cheapest links, A-C and B-C, for a total of 4; the A-to-B route inside that tree costs 4, while the direct A-B trench costs only 3, and the MST simply left it out. So an MST is the right answer to "cable every office for the least total money" and the wrong answer to "what is the fastest path from A to B".
go deeper
Be ready to say in one breath that an MST minimizes total connection cost, not the cost between a chosen pair, and to sketch a three-node counterexample on the spot.
Explain that the two structures optimize different objectives — one sum versus one distance per node — and name which problem each belongs to when the interviewer describes a scenario.
Show you catch the confusion in a design review: someone proposes an MST for a latency-routing feature, and you redirect them to a shortest-path formulation before the ticket is written.
Own the modeling decision: state what the business is actually paying for — total build-out spend, per-route latency, or worst-link resilience — because each of those maps to a different tree and a different algorithm.
## The two questions people confuse A **spanning tree** of a connected, undirected graph with `V` nodes is any subset of edges that connects all `V` nodes with no cycle. Every spanning tree has exactly `V-1` edges — that count is forced by the structure, not by the weights. A **minimum spanning tree (MST)** is the spanning tree whose edge weights add up to the smallest possible total. A **shortest-path tree** is a different object. Fix one source node; for every other node, take a cheapest path from the source to it. The union of those paths forms a tree rooted at the source. It minimizes `V-1` separate quantities (one distance per node), not a single sum. Both are trees on the same graph, both have `V-1` edges, and both come out of greedy algorithms — which is exactly why candidates blur them. ## The counterexample to keep in your pocket Three branch offices, with the cost of digging a fiber trench on each link: | Link | Trench cost | |---|---| | A-B | 3 | | A-C | 2 | | B-C | 2 | A spanning tree here needs two of the three links. The options cost 3+2 = 5, 3+2 = 5, or 2+2 = 4. The MST is `{A-C, B-C}` at total 4, and it **omits A-B**. Now ask the pair question: how expensive is the A-to-B route inside that tree? It is A→C→B = 4. But the graph itself offers A-B directly for 3. The MST is optimal for total cabling spend and simultaneously 33% worse than available for that one route. Nothing is broken — the MST never claimed otherwise. Notice the direction of the claim. "Minimum" in MST attaches to a **sum over the whole tree**. It does not distribute down to individual pairs, any more than the cheapest total grocery bill guarantees the cheapest price on any one item. ## What the MST path *does* guarantee There is a real per-pair property, and it is a good thing to know: the path between two nodes in an MST is a **minimum bottleneck path**. Among all paths between those nodes in the graph, it minimizes the *heaviest single edge* used, even though it may not minimize the total. In the triangle above, the A→C→B route uses a maximum edge of 2, while the direct A-B link is a single edge of 3 — so the tree route really is the better one under the bottleneck lens. That is the sense in which an MST is "good for connectivity": it keeps the worst link on every route as light as possible, not the sum on every route as small as possible. This is why MSTs show up in network design, clustering (cut the heaviest MST edges and the components fall out), and approximation schemes for tour problems — all of which care about the whole structure or the worst link, not about one pair's total. ## When they do coincide On a graph where every edge has the same weight, every spanning tree is minimum, and a breadth-first tree from the source is both an MST and a shortest-path tree. On a star-shaped graph where the source touches everything, the same set of edges is again both. Coincidence in special cases is not a general rule, and interviewers probe exactly this: "so if I need the cheapest route from headquarters to each office, do I build an MST?" The answer is no — that is a shortest-path problem from a single source, and it wants a different algorithm. ## Two more directional details - **Negative weights are fine for an MST.** The definition only involves summing a chosen edge set, and the greedy correctness argument compares crossing edges by weight; nothing assumes positivity. Several shortest-path methods, by contrast, break outright on negative edges. So "negative weights, therefore hard" is not a reflex you should apply here. - **The MST is not unique in general.** If all edge weights are distinct, the MST is unique. With ties — a very common case when weights are round numbers like trench costs in whole currency units — several different edge sets can share the same minimum total, and different algorithms, or the same algorithm with a different tie-break, may return different ones. Any of them is correct. If a downstream system needs a stable answer across runs, the fix is a deterministic tie-break rule, not a claim that the MST was unique all along.
- So what does the path between two nodes inside an MST actually optimize?It is a minimum bottleneck path: among all paths between those two nodes, it minimizes the weight of the heaviest edge used, though not the total weight. In the 3-2-2 triangle, the two-hop tree route has a maximum edge of 2 while the direct link is 3, so the tree route wins on the bottleneck measure and loses on the sum.
- Do negative edge weights break minimum spanning tree construction?No. An MST only sums a chosen edge set, and the greedy safety argument compares the weights of edges crossing a partition; neither step assumes weights are positive. Shifting every weight by a constant also leaves the MST unchanged, since every spanning tree has the same edge count. Negative weights break some shortest-path methods, which is where that reflex comes from.
- Can a graph have more than one minimum spanning tree?Yes, whenever edge weights tie. Distinct weights guarantee a unique MST, but with ties several edge sets can hit the same minimum total, and different algorithms or tie-break orders return different ones — all correct. If a caller needs a reproducible answer, impose a deterministic tie-break, such as ordering equal-weight edges by node identifier.
The cheapest way to wire a whole building is not the cheapest wire between any two particular rooms; a global bill and a per-pair bill are different bills.
saying these in an interview costs you the question
- Says the MST contains the shortest path between any two nodes
- Claims MST and single-source shortest-path tree are the same tree
- Thinks the MST always includes the globally cheapest edge touching each node
- Assumes negative edge weights make an MST undefined
- Assumes the MST is always unique