## Minimum Number of Wagons to Connect Every City in Ticket to Ride – Europe

How many wagons would you need to create a route network in the board game Ticket to Ride – Europe so that every city is connected to every other city through the network?  If you could do this you could potentially earn every destination ticket in the game.

To answer this question, we first need to make a graph out of the Ticket to Ride – Europe map.  We need to represent each city by a vertex, and we need to represent each city-to-city route by an arc with weight equal to the number of wagons it takes to claim that particular route.  Then the question entails finding a minimum spanning tree that connects all the vertices in this graph.  The total weight of the minimum spanning tree will be the answer to our question.

Fortunately, there are some fast algorithms for finding minimum spanning trees, and some of them are simple enough that we can easily perform them by hand.  For this post we’ll use Prim’s algorithm, which involves the following steps:

1. Start at any vertex to initialize the tree.
2. Select a minimum-weight arc that is not in the tree but that connects a vertex in the tree with one not in the tree.  Add that arc and the new vertex to the tree.
3. Repeat Step 2 until all vertices are in the tree.

Edinburgh is a logical city in which to start, since from there the only choice for arc is the 4-wagon route to London.  Add London and the route from Edinburgh to London to our tree.

Now, there are two minimum-weight arcs out of Edinburgh or London to new cities.  These are the two-wagon routes from London to Amsterdam and from London to Dieppe.  It actually doesn’t matter which one we pick; the proof of correctness for Prim’s algorithm tells us that either would lead to a minimum spanning tree, even if we don’t eventually choose the other route for our tree.  Let’s take alphabetical order as the tiebreaker and choose the London to Amsterdam route for two wagons.

In the next iteration the shortest route available to us isn’t the two-wagon route from London to Dieppe; it’s the one-wagon route from Amsterdam to Bruxelles.  So we must take that one.

Next iteration: There are multiple two-wagon routes available now: London to Dieppe, Bruxelles to Dieppe, Bruxelles to Paris, Bruxelles to Frankfurt, and Amsterdam to Frankfurt.  Alphabetical order for the new city gives us Dieppe, and alphabetical order again would select Bruxelles over London as the city to connect Dieppe to.  (Again, any of these choices would give us a minimum spanning tree at the end, so all we need is some tiebreaker criterion.)

Next choice is Dieppe to Paris for one wagon.

In the next iteration there are multiple two-wagon routes available again: Dieppe to Brest, Bruxelles to Frankfurt, and Amsterdam to Frankfurt.  We do not include the London-to-Dieppe route or the Bruxelles-to-Paris route because we only consider arcs from cities already in our tree to new cities.  Alphabetical order as the tiebreaker criterion means we select Dieppe to Brest as our new arc.

From here, I’ll just list the remaining arcs that are added, in order of selection (again using our alphabetical order tiebreaker).  For completeness I’ll include the arcs and vertices we’ve already selected.

1. Edinburgh (start)
2. Edinburgh to London (4 wagons)
3. London to Amsterdam (2)
4. Amsterdam to Bruxelles (1)
5. Bruxelles to Dieppe (2)
6. Dieppe to Paris (1)
7. Dieppe to Brest (2)
8. Amsterdam to Frankfurt (2)
9. Frankfurt to Essen (2)
10. Essen to Berlin (2)
11. Frankfurt to Munchen (2)
12. Munchen to Venezia (2)
13. Venezia to Roma (2)
14. Roma to Brindisi (2)
15. Venezia to Zagrab (2)
16. Zagrab to Budapest (2)
17. Budapest to Wien (1)
18. Munchen to Zurich (2)
19. Zurich to Marseille (2)
20. Essen to Kobenhavn (3)
21. Brindisi to Palermo (3)
22. Budapest to Sarajevo (3)
23. Sarajevo to Sofia (2)
24. Sofia to Bucuresti (2)
25. Sofia to Athina (3)
26. Athina to Smyrna (2)
27. Smyrna to Constantinople (2)
28. Constantinople to Angora (2)
29. Angora to Erzurum (3)
30. Erzurum to Sochi (3)
31. Sochi to Rostov (2)
32. Rostov to Kharkov (2)
33. Sochi to Sevastopol (2)
34. Kobenhavn to Stockholm (3)
35. Marseille to Barcelona (4)
37. Barcelona to Pamplona (2)
40. Berlin to Danzig (4)
41. Danzig to Warszawa (2)
42. Danzig to Riga (3)
43. Warszawa to Wilno (3)
44. Wilno to Kyiv (2)
45. Kyiv to Smolensk (3)
46. Smolensk to Moskva (2)