Spanning Trees and Route Problems: 10 Applications, Worked Step by Step

Fiber-Optic Cable Between Seven Buildings on a College Campus, and a Trench That Cannot Be Dug

methodTake the Trenches from Shortest to Longest, Keeping Each One Unless It Joins Two Buildings That Are Already Connected

A college will lay fiber-optic cable in trenches so that all seven of its buildings are connected, directly or through other buildings: the admin building A, the cafeteria C, the dormitory D, the gym G, the library L, the music school M and the science block S. The trenches that can be dug, with their lengths in meters, are A–L 85, A–C 90, A–D 120, L–C 70, L–G 110, L–S 150, S–G 95, C–G 105, C–D 100, C–M 140, G–M 60 and D–M 160. No two lengths are equal. (a) Use Kruskal's algorithm to list the trenches in the order they are chosen, naming any trench it rejects on the way, and find the least total length of trench. (b) A survey then finds a gas main under the route of trench C–G, so C–G cannot be dug. What is the least total length now, and which trench takes the place of C–G?

The trenches sorted from shortest to longest.

Sort the trenches by length: G–M 60, L–C 70, A–L 85, A–C 90, S–G 95, C–D 100, C–G 105, L–G 110, A–D 120, C–M 140, L–S 150, D–M 160.

step 1 of 6

Kruskal's algorithm builds the shortest network one trench at a time. Take the trenches from shortest to longest, and keep each one unless both of its buildings are already connected, because then it would only close a cycle.

Sort the trenches by length: G–M 60, L–C 70, A–L 85, A–C 90, S–G 95, C–D 100, C–G 105, L–G 110, A–D 120, C–M 140, L–S 150, D–M 160.
Take G–M (60), L–C (70) and A–L (85), since none of them closes a cycle. Reject A–C (90): A and C are already connected through L, so it would close the cycle A–L–C.
Take S–G (95) and C–D (100). The buildings now form two groups, A, L, C, D and G, M, S. C–G (105) joins the two groups, so take it. Six trenches now connect all seven buildings, and the algorithm stops.
(a) The order is G–M, L–C, A–L, S–G, C–D, C–G, with A–C rejected. The least total length is 60 + 70 + 85 + 95 + 100 + 105 = 515 m.
Without C–G, the algorithm makes the same choices up to C–D, and the two groups are still separate. The next trench in the list is L–G (110), and it joins the group A, L, C, D to the group G, M, S.
(b) L–G takes the place of C–G, and the least total length is now 515 − 105 + 110 = 520 m. Check: 60 + 70 + 85 + 95 + 100 + 110 = 520.

answer(a) G–M (60), L–C (70), A–L (85), S–G (95), C–D (100), C–G (105), with A–C rejected; the least total length is 515 m. (b) 520 m, with L–G in place of C–G

techniqueKruskal’s Algorithm for a Spanning Tree

Common pitfalls

Taking A–C (90 m) because it is the next shortest trench. A and C are already connected through L, so A–C closes the cycle A–L–C and adds 90 m that connects nothing new.
Stopping as soon as every building has a trench at it. After C–D every building has one, but the buildings still form two separate groups, A, L, C, D and G, M, S, and one more trench is needed to join them.

Irrigation Pipes From a Farm's Pump to Five Fields, Planned From a Table of Distances

methodGrow One Network Outward From the Pump, Each Time Taking the Shortest Pipe From a Site Already Joined to a Site Not Yet Joined

A farmer will lay water pipes so that the pump P supplies five fields A, B, C, D and E, each field fed straight from the pump or through the pipes to other fields. The table gives the length in meters of the pipe needed between each pair of sites: P–A 42, P–B 55, P–C 70, P–D 38, P–E 64, A–B 30, A–C 48, A–D 50, A–E 36, B–C 40, B–D 61, B–E 57, C–D 39, C–E 52, D–E 33. No two lengths are equal. (a) Use Prim's algorithm, starting at the pump, to find the order in which the fields are joined, the pipe that joins each one, and the least total length of pipe. (b) Her first plan was a separate pipe from the pump to each field. How much pipe does the network from (a) save compared with that plan?

The shortest entry in the pump's row is P–D, 38 m. Each pipe is ringed in the row of the field it joins.

Start at the pump. The shortest entry in P's row is P–D, 38 m, so D is joined first.

step 1 of 5

Prim's algorithm grows a single network from the starting site. At each step, look at every site already joined, and take the shortest pipe from any of them to a site that is not yet joined.

Start at the pump. The shortest entry in P's row is P–D, 38 m, so D is joined first.
From P and D, the pipes to new fields are P–A 42, P–B 55, P–C 70, P–E 64, D–A 50, D–B 61, D–C 39 and D–E 33. The shortest is D–E, so E is joined second.
From P, D and E, the shortest pipe to a new field is E–A, 36 m, shorter than D–C at 39 m, so A is joined third. From P, D, E and A, the shortest is A–B, 30 m, so B is joined fourth.
Only C is left. Its pipes to joined sites are D–C 39, B–C 40, A–C 48, C–E 52 and P–C 70, so C is joined by D–C. (a) The order is D, E, A, B, C, by the pipes P–D, D–E, E–A, A–B and D–C, with a total of 38 + 33 + 36 + 30 + 39 = 176 m.
A separate pipe from the pump to each field needs 42 + 55 + 70 + 38 + 64 = 269 m. (b) The network saves 269 − 176 = 93 m of pipe.

answer(a) D by P–D, E by D–E, A by E–A, B by A–B, C by D–C; the total is 176 m. (b) 93 m

techniquePrim’s Algorithm and the Matrix Method

Common pitfalls

Looking only in the row of the field joined last. From B the shortest pipe to C is 40 m, but D was joined earlier and D–C is 39 m: Prim's algorithm compares the rows of every site already joined.
Starting with the shortest pipe in the whole table, A–B at 30 m. That is how Kruskal's algorithm begins; Prim's algorithm from the pump must begin with a pipe at the pump.

A Fiber Network Joining Six Public Buildings in a County, When the Hospital and the Fire Station Must Be Linked Directly

methodRun Kruskal's Algorithm for the Shortest Network; for the Required Link, Put It In First and Then Run the Algorithm on the Other Routes

A county will join six public buildings with fiber-optic cable: the hospital H, the fire station F, the police station P, the school S, the town hall T and the water works W. The possible cable routes, with lengths in kilometers, are P–H 6, H–T 7, P–S 9, P–F 8, H–F 11, T–F 5, T–W 10, S–F 4 and F–W 3. No two lengths are equal. (a) What is the least total length of cable that connects all six buildings? (b) The emergency plan requires a direct cable between the hospital and the fire station, so that messages between them never pass through another building. What is the least total length now, and which cable from (a) is no longer needed?

The routes sorted from shortest to longest.

Sort the routes by length: F–W 3, S–F 4, T–F 5, P–H 6, H–T 7, P–F 8, P–S 9, T–W 10, H–F 11.

step 1 of 5

Kruskal's algorithm gives the shortest network. A cable that must be included is laid first, and the algorithm then runs on the other routes as usual, rejecting any route that would close a cycle.

Sort the routes by length: F–W 3, S–F 4, T–F 5, P–H 6, H–T 7, P–F 8, P–S 9, T–W 10, H–F 11.
Take F–W, S–F and T–F, which join W, S and T to F, and then P–H. Take H–T (7), which joins the pair H, P to the group F, S, T, W. Five cables now connect all six buildings.
(a) The least total length is 3 + 4 + 5 + 6 + 7 = 25 km.
For (b), lay H–F (11) first, then take the other routes in order. F–W, S–F, T–F and P–H are taken as before, and with H–F they already connect all six buildings. H–T is rejected, because H and T are already connected through F.
(b) The least total length is 11 + 3 + 4 + 5 + 6 = 29 km, which is 4 km more, and the cable H–T is no longer needed. Check: adding H–F to the network from (a) makes the cycle H–F–T–H, and removing the longest other cable on it, H–T at 7 km, gives 25 + 11 − 7 = 29 km.

answer(a) 25 km; (b) 29 km, and H–T is no longer needed

techniqueKruskal’s Algorithm for a Spanning Tree

Common pitfalls

Adding H–F to the network from (a) and keeping all five other cables, 25 + 11 = 36 km. H–F closes the cycle H–F–T–H, so one cable on that cycle is no longer needed.
Running the algorithm in plain order and waiting for H–F to come up at 11 km. By then all six buildings are connected, so H–F is rejected and the requirement is not met.

Cables Between a Wind Farm's Substation and Four Turbines, and a Fifth Turbine Approved Before Building Starts

methodGrow the Network From the Substation With Prim's Algorithm, Then Plan the Whole Network Again With the New Site Included

A wind farm will join its substation S and four turbines A, B, C and D with underground cable. Each turbine must be linked to the substation directly or through other turbines, and cables can meet only at a turbine or at the substation. The cable routes that can be used, with lengths in meters, are S–A 400, S–B 650, A–B 500, A–C 700, B–C 450, B–D 800 and C–D 550. (a) Use Prim's algorithm, starting at S, to find the order in which the turbines are joined and the least total length of cable. (b) Before any cable is laid, a fifth turbine N is approved. It can be joined to B by 350 m, to C by 300 m and to D by 250 m of cable. What is the least total length of cable for all six sites now?

From S, the shorter route is S–A, 400 m.

From S, the routes are S–A 400 m and S–B 650 m. The shorter is S–A, so A is joined first.

step 1 of 5

Prim's algorithm grows the network from the substation, each time taking the shortest cable from a site already joined to a site not yet joined. Since nothing has been laid, the network for (b) is planned again from the start.

From S, the routes are S–A 400 m and S–B 650 m. The shorter is S–A, so A is joined first.
From S and A, the routes to new turbines are S–B 650, A–B 500 and A–C 700, so A–B joins B. From S, A and B, the shortest is B–C, 450 m, so C is joined next, and then C–D (550 m, against B–D at 800 m) joins D.
(a) The order is A, B, C, D, and the least total length is 400 + 500 + 450 + 550 = 1900 m.
With N, run the algorithm again from S. It takes S–A and A–B as before. From S, A and B the shortest route is now B–N, 350 m. From these four sites the shortest is N–D, 250 m, and then N–C, 300 m, which is shorter than B–C at 450 m.
(b) The least total length is 400 + 500 + 350 + 250 + 300 = 1800 m. Check: the five cables join all six sites without a cycle, and the new plan drops B–C and C–D (1000 m) for B–N, N–C and N–D (900 m), so it is 100 m shorter than the plan for four turbines.

answer(a) A, B, C, D, with a total of 1900 m; (b) 1800 m

techniquePrim’s Algorithm and the Matrix Method · Kruskal’s Algorithm for a Spanning Tree

Common pitfalls

Keeping the network from (a) and adding N by its shortest cable, N–D at 250 m, to get 1900 + 250 = 2150 m. Nothing has been laid yet, so the whole network is planned again, and routing through N replaces two longer cables.
Rejecting 1800 m because six sites should need more cable than five. Cables may meet at N, and N sits close to B, C and D, so its three short cables together are shorter than B–C and C–D.

A Salt Truck That Must Spread Salt on Every Street of a Neighborhood and Return to Its Depot

methodFind the Junctions Where an Odd Number of Streets Meet, Pair Them in Each of the Three Possible Ways, and Repeat the Shortest Routes of the Pairing With the Least Total

A salt truck must drive along every street of a neighborhood at least once, starting and finishing at its depot at junction A. One pass salts the whole width of a street. The streets, with their lengths in meters, are A–B 320, B–C 280, A–D 250, B–E 400, C–F 260, D–E 300, E–F 420, B–D 460 and B–F 600. (a) Which streets must the truck drive twice on a shortest route? (b) How long is that shortest route?

Four junctions have an odd number of streets: B, D, E and F.

Count the streets at each junction: A has 2, B has 5, C has 2, D has 3, E has 3 and F has 3. The odd junctions are B, D, E and F.

step 1 of 5

A closed route that drives every street exactly once needs an even number of streets at every junction. Where the count is odd, some streets must be driven twice: pair up the odd junctions so that the routes joining the pairs are as short as possible in total.

Count the streets at each junction: A has 2, B has 5, C has 2, D has 3, E has 3 and F has 3. The odd junctions are B, D, E and F.
Four odd junctions can be paired in three ways. The shortest routes are B–D 460 and E–F 420; B–E 400 and D–F 720 (by D–E–F); B–F 540 (by B–C–F, shorter than the street B–F at 600) and D–E 300.
The three pairings total 460 + 420 = 880, 400 + 720 = 1120 and 540 + 300 = 840 m. The least is 840 m, pairing B with F and D with E.
(a) The truck drives B–C, C–F and D–E twice. With these repeats, every junction has an even number of passes, so a closed route over every street exists.
The streets total 320 + 280 + 250 + 400 + 260 + 300 + 420 + 460 + 600 = 3290 m. (b) The shortest route is 3290 + 840 = 4130 m.

answer(a) B–C, C–F and D–E; (b) 4130 m

techniqueThe Chinese Postman Problem

Common pitfalls

Repeating the street B–F (600 m) to pair B with F. The route B–C–F is only 540 m, so the streets driven twice are B–C and C–F.
Pairing B with its nearest odd junction, E (400 m), and then having to pair D with F at 720 m, a total of 1120 m. The pairings must be compared by their totals, not one pair at a time.

A Park Ranger Checking Every Path After a Storm, From the Main Gate or Between Any Two Junctions

methodPair the Odd Junctions for a Closed Route; for an Open Route, End at Two Odd Junctions and Repeat Only the Shortest Route Joining the Other Two

After a storm, a park ranger must walk along every path of a park at least once to check for fallen trees. The paths, with their lengths in meters, are G–H 150, G–K 170, H–M 130, K–M 140, M–N 190, M–R 160, N–R 230, H–N 280 and K–R 260, where G is the main gate. (a) How long is the shortest route that starts and finishes at G? (b) Instead, a colleague can drop her off by cart at any junction and collect her at any other. Where should she start and finish, and how long is her shortest route then?

The gate G has two paths. H, K, N and R have an odd number.

Count the paths at each junction: G 2, H 3, K 3, M 4, N 3, R 3. The odd junctions are H, K, N and R. The paths total 150 + 170 + 130 + 140 + 190 + 160 + 230 + 280 + 260 = 1710 m.

step 1 of 5

Every junction with an odd number of paths forces a repeat. A closed route pairs all the odd junctions; an open route starts and finishes at two of them, so only the other two need joining by repeated paths.

Count the paths at each junction: G 2, H 3, K 3, M 4, N 3, R 3. The odd junctions are H, K, N and R. The paths total 150 + 170 + 130 + 140 + 190 + 160 + 230 + 280 + 260 = 1710 m.
Find the shortest route between each pair of odd junctions: H–K 270 (by H–M–K), N–R 230, H–N 280, K–R 260, H–R 290 (by H–M–R) and K–N 330 (by K–M–N).
The three pairings total 270 + 230 = 500, 280 + 260 = 540 and 290 + 330 = 620 m. (a) The least is 500 m, repeating H–M, M–K and N–R, so the shortest closed route is 1710 + 500 = 2210 m.
An open route starts and finishes at two odd junctions, and only the other two need a repeated route between them. The shortest of the six routes is N–R at 230 m, so she should leave H and K as the ends.
(b) She should start at H and finish at K, or the other way round, and the route is 1710 + 230 = 1940 m.

answer(a) 2210 m; (b) start at H and finish at K (or the reverse), 1940 m

techniqueThe Chinese Postman Problem

Common pitfalls

Starting and finishing at N and R because they are joined by the shortest route. The shortest route is the one she walks twice, so N and R are the junctions to join, and H and K are the ends.
Taking the pairing from (a) and dropping the wrong repeat. Keeping H–M–K and leaving out N–R gives 1710 + 270 = 1980 m; all six routes must be compared, and the shortest one is kept.

A Delivery Van's Round Trip From Its Depot to Five Stores, and a Second Starting Point for the Nearest-Neighbor Algorithm

methodRun the Nearest-Neighbor Algorithm From Each Named Start, Close Each Tour, and Compare the Two Upper Bounds

A delivery van leaves its depot D, visits five stores A, B, C, E and F, and returns to D. The table gives the shortest road distances in kilometers: D–A 13, D–B 38, D–C 21, D–E 34, D–F 10, A–B 28, A–C 12, A–E 24, A–F 16, B–C 19, B–E 8, B–F 37, C–E 15, C–F 20, E–F 31. No two distances are equal, so the algorithm never has to break a tie. (a) Use the nearest-neighbor algorithm starting at D to find a round trip and its length. (b) Run the algorithm again starting at store A. Which of the two round trips gives the better upper bound for the shortest round trip, and what is that bound?

Each leg is ringed in the row of the place it leaves: D to F, F to A, A to C.

From D the nearest store is F (10 km). From F the nearest store not yet visited is A (16 km), and from A it is C (12 km).

step 1 of 5

The nearest-neighbor algorithm goes each time to the nearest place not yet visited, then returns to the start. Any round trip it finds is one the van can drive, so its length is an upper bound for the shortest round trip.

From D the nearest store is F (10 km). From F the nearest store not yet visited is A (16 km), and from A it is C (12 km).
From C the nearest store not yet visited is E (15 km, against B at 19 km), and from E it is B (8 km). Every store has now been visited, so the van returns from B to D (38 km).
(a) The round trip is D–F–A–C–E–B–D, of length 10 + 16 + 12 + 15 + 8 + 38 = 99 km.
From A the nearest place is C (12 km), then E (15 km), then B (8 km). From B the nearest place not yet visited is F (37 km, against D at 38 km), then D (10 km), and the trip returns from D to A (13 km). Its length is 12 + 15 + 8 + 37 + 10 + 13 = 95 km.
This round trip is a cycle, so the van can drive it starting from the depot, as D–A–C–E–B–F–D. (b) The trip found from A is shorter, so the better upper bound is 95 km: the shortest round trip is at most 95 km.

answer(a) D–F–A–C–E–B–D, 99 km; (b) the round trip from A, driven as D–A–C–E–B–F–D, gives the better upper bound of 95 km

techniqueThe Nearest-Neighbor Upper Bound · The Traveling Salesman Problem

Common pitfalls

Leaving out the last leg back to the start. The round trip must close, and the return from B to D adds 38 km to the trip in (a).
Choosing the larger length, 99 km, as the better upper bound. Both trips can be driven, so the shortest round trip is at most each of them, and the smaller one, 95 km, says more.

A Technician Servicing Six Weather Stations, and the Least Length a Round Trip Could Have

methodDelete One Station, Find a Minimum Spanning Tree of the Other Five, and Add the Two Shortest Roads at the Deleted Station

A technician drives round six weather stations A, B, C, D, E and F in a national park, visiting each one once and returning to the station where she started. The table gives the shortest road distances in kilometers: A–B 27, A–C 16, A–D 18, A–E 21, A–F 15, B–C 37, B–D 11, B–E 34, B–F 28, C–D 30, C–E 12, C–F 13, D–E 29, D–F 22, E–F 9. (a) Find a lower bound for the length of her round trip by deleting station A. (b) Find the lower bound given by deleting station B. Which of the two is the better lower bound?

With A deleted, the minimum spanning tree of the other five is 54 km. Each edge is ringed once.

Delete A and every road at A. Kruskal's algorithm on B, C, D, E and F takes E–F (9), B–D (11) and C–E (12), rejects C–F (13) because C and F are already joined through E, and takes D–F (22). The tree is 9 + 11 + 12 + 22 = 54 km.

step 1 of 5

Take one station out of a round trip and what is left is a path through the other five, which is at least as long as their minimum spanning tree. The trip also uses two roads at the deleted station, which are at least its two shortest.

Delete A and every road at A. Kruskal's algorithm on B, C, D, E and F takes E–F (9), B–D (11) and C–E (12), rejects C–F (13) because C and F are already joined through E, and takes D–F (22). The tree is 9 + 11 + 12 + 22 = 54 km.
The two shortest roads at A are A–F (15) and A–C (16). (a) The lower bound is 54 + 15 + 16 = 85 km.
Delete B instead. On A, C, D, E and F the algorithm takes E–F (9) and C–E (12), rejects C–F (13), takes A–F (15), rejects A–C (16) because A and C are already joined through F and E, and takes A–D (18). The tree is 9 + 12 + 15 + 18 = 54 km.
The two shortest roads at B are B–D (11) and A–B (27), so this lower bound is 54 + 11 + 27 = 92 km.
(b) Deleting B gives 92 km. Every round trip is at least 85 km and at least 92 km, so the better lower bound is the higher one, 92 km.

answer(a) 85 km; (b) 92 km, which is the better lower bound

techniqueThe Deleted-Vertex Lower Bound · Kruskal’s Algorithm for a Spanning Tree

Common pitfalls

Adding only the shortest road at the deleted station. A round trip arrives at the station and leaves it again, so it uses two roads there.
Taking the smaller value, 85 km, as the better lower bound. Both bounds are true, so every round trip is at least 92 km, and the higher bound says more.

A Hospital Lab's Courier Collecting Samples From Five Clinics, and Whether a Driver's Proposed Route Is the Shortest

methodBound the Shortest Round Trip Above by Nearest Neighbor and Below by Deleting a Vertex, Then Compare the Proposed Route With the Lower Bound

A courier leaves the hospital lab L, collects samples from five clinics A, B, C, D and E, and returns to L. The table gives the shortest road distances in kilometers: L–A 27, L–B 5, L–C 17, L–D 8, L–E 14, A–B 30, A–C 16, A–D 29, A–E 25, B–C 20, B–D 6, B–E 13, C–D 21, C–E 22, D–E 9. No two distances are equal. (a) Use the nearest-neighbor algorithm starting at L for an upper bound, and delete clinic A for a lower bound. Between which two values does the length of the shortest round trip lie? (b) A driver proposes the route L–C–A–E–D–B–L. Find its length, and decide whether any round trip is shorter.

Nearest neighbor from L gives a round trip of 85 km, an upper bound.

Nearest neighbor from L: L to B (5 km), B to D (6), D to E (9), E to C (22, against A at 25), C to A (16), and back from A to L (27). This round trip is 5 + 6 + 9 + 22 + 16 + 27 = 85 km, an upper bound.

step 1 of 5

A round trip found by any method is an upper bound for the shortest, and the deleted-vertex method gives a lower bound. A route whose length equals the lower bound cannot be beaten.

Nearest neighbor from L: L to B (5 km), B to D (6), D to E (9), E to C (22, against A at 25), C to A (16), and back from A to L (27). This round trip is 5 + 6 + 9 + 22 + 16 + 27 = 85 km, an upper bound.
Delete A. Kruskal's algorithm on L, B, C, D and E takes L–B (5) and B–D (6), rejects L–D (8), takes D–E (9), rejects B–E (13) and L–E (14), and takes L–C (17). The tree is 5 + 6 + 9 + 17 = 37 km.
The two shortest roads at A are A–C (16) and A–E (25), so the lower bound is 37 + 16 + 25 = 78 km. (a) The shortest round trip is at least 78 km and at most 85 km.
The proposed route is L–C 17, C–A 16, A–E 25, E–D 9, D–B 6 and B–L 5, a total of 17 + 16 + 25 + 9 + 6 + 5 = 78 km.
(b) The route is 78 km. No round trip can be shorter than the lower bound of 78 km, and this route equals it, so no round trip is shorter. Check: without A the route is the path C–L–B–D–E, which is the tree from the second step, and it uses the two shortest roads at A.

answer(a) Between 78 km and 85 km; (b) 78 km, and no round trip is shorter

techniqueThe Deleted-Vertex Lower Bound · The Nearest-Neighbor Upper Bound · The Traveling Salesman Problem

Common pitfalls

Doubting the proposed route because the nearest-neighbor trip is 85 km. The upper bound says only that the shortest trip is at most 85 km; a 78 km route is allowed, and meeting the lower bound makes it the shortest.
Assuming that some route always reaches the lower bound. In general the shortest round trip can be longer than the bound; here a route is known to be the shortest only because its length equals the bound.

A Vet's Round Trip From Her Base to Four Farms on Country Roads That Do Not Join Every Pair

methodReplace Each Pair of Places by Its Shortest Route to Complete the Table, Run Nearest Neighbor on the Table, Then Write the Round Trip Back on the Roads

A vet based at B drives out to four farms P, Q, R and S and back to B. The country roads, with their lengths in kilometers, are B–P 8, B–Q 11, P–Q 6, P–R 9, Q–R 14, Q–S 7 and R–S 5, and there is no other road. The vet may pass a farm again on her way to another. (a) Find the shortest distance by road for each of the pairs B–R, B–S, P–S and Q–R. (b) Use the nearest-neighbor algorithm, starting at B, on the table of shortest distances. How long is the round trip, and in what order does the vet drive through the places on the roads?

B–R has no road: the shortest route is B–P–R, 17 km. B–S is B–Q–S, 18 km.

There is no road B–R. The route B–P–R is 8 + 9 = 17 km and B–Q–R is 11 + 14 = 25 km, so B–R is 17 km. For B–S, the route B–Q–S is 11 + 7 = 18 km, shorter than B–P–Q–S (21) and B–P–R–S (22).

step 1 of 5

The nearest-neighbor algorithm needs a distance for every pair of places, so each pair gets the length of its shortest route on the roads. The round trip found on that table is then written back as the roads actually driven.

There is no road B–R. The route B–P–R is 8 + 9 = 17 km and B–Q–R is 11 + 14 = 25 km, so B–R is 17 km. For B–S, the route B–Q–S is 11 + 7 = 18 km, shorter than B–P–Q–S (21) and B–P–R–S (22).
For P–S, the route P–Q–S is 6 + 7 = 13 km, against P–R–S at 9 + 5 = 14 km. Q–R has a road of 14 km, but Q–S–R is only 7 + 5 = 12 km. (a) The shortest distances are B–R 17, B–S 18, P–S 13 and Q–R 12 km.
On the completed table, go from B to P (8, against Q at 11), from P to Q (6), from Q to S (7, against R at 12), from S to R (5), and back from R to B (17).
The round trip B–P–Q–S–R–B is 8 + 6 + 7 + 5 + 17 = 43 km.
(b) The round trip is 43 km. Its last leg, R to B, is the route R–P–B on the roads, so the vet drives B, P, Q, S, R, P, B, passing P twice.

answer(a) B–R 17 km, B–S 18 km, P–S 13 km, Q–R 12 km; (b) 43 km, driven B, P, Q, S, R, P, B

techniqueThe Traveling Salesman Problem · The Nearest-Neighbor Upper Bound

Common pitfalls

Using the road Q–R, 14 km, as the table entry. The table holds the shortest distance, and the route through S is 12 km.
Rejecting the round trip because it passes P twice. The vet visits each farm once; passing P again on the way home is simply the shortest road from R to B.