Connector problems and best paths

Solving minimal connector problems with minimum spanning trees, and why the shortest path is not always in the tree or the best choice.

You now have two tools: the shortest path and the minimum spanning tree. The hard part in an exam is usually not running the method. It's reading a worded problem and deciding which tool it needs.

Minimal connector problems

A minimal connector problem asks you to link every location using the least total length, time or cost. Laying NBN fibre to every house in a new estate, running irrigation pipe to every paddock, or building walking tracks between campsites are all minimal connector problems. The answer is a minimum spanning tree.

The question says…	Use
"connect all", "link every", "least cable/pipe to reach each"	minimum spanning tree
"from X to Y", "quickest route", "shortest trip"	shortest path

Example 1●●

A farm near Dubbo needs water piped from a tank to a house (H), a shed (S), a dam (D) and a paddock trough (P). The tank is T. Possible pipe routes and their lengths in metres are shown. Pipe costs $\$18$ per metre laid. Find the minimum cost.

Use Kruskal's algorithm

Every site must be reached, and only the total length matters. That's a minimal connector problem, so find a minimum spanning tree.

Keep ST $70$, DP $80$, HT $90$

Sort the edges: ST 70, DP 80, HT 90, TD 110, HS 120, TP 130, SP 150, HD 200.

Keep TD $110$. That's $4$ edges for $5$ vertices, so stop.

T's group is {S, T, H} and D's group is {D, P}. TD joins the two groups, so it makes no cycle.

Total pipe $= 70 + 80 + 90 + 110 = 350$ m

Add the lengths.

Cost $= 350 \times 18 = 6300$, so $\$6300$

Multiply by the cost per metre.

Pipe routes on the farm in metres. The minimum spanning tree is in orange.

Shortest paths and spanning trees are different

It's natural to assume the minimum spanning tree also gives the shortest trips. It doesn't. The tree minimises the total of all its edges. A shortest path minimises one particular journey. These are different goals, so they often give different edges.

A network with its minimum spanning tree in orange (total weight 13).

Example 2●●

For the network above: (a) find the shortest path from A to E (b) find the length of the route from A to E using only the minimum spanning tree (c) explain the difference.

A–C–D–E $= 7 + 3 + 2 = 12$, A–B–C–D–E $= 4 + 4 + 3 + 2 = 13$, A–B–D–E $= 4 + 7 + 2 = 13$, A–C–E $= 7 + 6 = 13$

List the sensible routes from A to E.

(a) A–C–D–E, length $12$

Smallest total.

(b) A–B–C–D–E, length $13$

In the tree, the only route from A to E is along the orange edges.

(c) The shortest path uses AC, which is not in the minimum spanning tree. The tree is cheapest overall, not for every trip.

The direct edge AC (7) is useful for this one trip, but the tree reaches C more cheaply through B (AB 4 + BC 4 = 8 for two vertices instead of 7 for one).

Is the shortest path the best path?

The shortest path is only "best" for the one thing the weights measure. Real decisions weigh up more than one thing:

Tolls: the shortest drive into the city might use a toll road. Is $5$ minutes worth the toll?
Traffic and time of day: a short road through Parramatta at 8 am may be slower than a longer motorway.
Road type and safety: a short dirt road, school zones, or roads unsuitable for a truck.
Accessibility: the shortest walk between platforms may have stairs and no lift.
Reliability: a route with one fragile link can be worse than a slightly longer route with options.

InteractiveShortest route, toll roads and the tree

Try this

For Penrith to the Sydney CBD, find the shortest route by distance, then by time. Are they the same?

Turn on Avoid toll roads. How much longer does the trip get?

Turn on Show minimum spanning tree and try each trip. For which trips does the shortest route leave the tree?

Your turn

In Example 1, the farmer decides the dam (D) doesn't need water after all. What is the new minimum length of pipe?

Show the working

Remove D and its edges. Remaining edges: ST $70$, HT $90$, HS $120$, TP $130$, SP $150$. Kruskal's: keep ST $70$, HT $90$, skip HS $120$ (cycle H–S–T), keep TP $130$. Total $= 70 + 90 + 130 = 290$ m. Losing DP and TD means the paddock now needs its own longer pipe.

Flashcards

Minimal connector problem

Connect every vertex for the least total weight: find a minimum spanning tree

Is the shortest path always in the MST?

No. The MST minimises the total, not each trip.

Why might the shortest path not be best?

Tolls, traffic, safety, road type, accessibility: the weights measure only one thing

Practice

A council wants to build bike paths so that every one of $8$ parks is connected, using the least total length of path. This is:
How many bike paths will the council's solution have?
In Example 1, what is the minimum cost in dollars of the pipe?
In Example 2's network, what is the length of the shortest path from A to C?
Which statement is true?
What is the total weight of the minimum spanning tree in Example 2?
A delivery driver wants the quickest route from a warehouse to one customer. They should find:
Exam style: In Example 1 the dam no longer needs water. Find the minimum length of pipe, in metres, to connect T, H, S and P.
Exam style: A maps app's shortest route from Westmead into the city saves $3$ km, but it uses a toll road and runs through two school zones. Which is the best reason to take a longer route?