Santa's Travel Plans
Silouhette of santa's sleigh


Santa's Travel Plans

Whilst staying in an Aberystwyth holiday home, Santa decides to make some present deliveries to grottos located in a number of towns around Mid Wales.

As Santa needs to have some rest during his pre-Christmas Eve break, he needs to find the route that will minimize the distance he must travel.

The table below gives the distances between each pair of towns, some of which are shown in this diagram:

Mapping of the points using the information from the adjacent table

All distances are in miles.

They represent the direct route 'as the sleigh flies', and are the same in both directions.

Aberystwyth Builth Wells Llanidloes Machynlleth Newtown Welshpool
Aberystwyth - 34 23 18 29 43
Builth Wells 34 - 27 36 26 37
Llanidloes 23 27 - 17 11 22
Machynlleth 18 36 17 - 17 30
Newtown 29 26 11 17 - 12
Welshpool 43 37 22 30 12 -

The challenge

Find the route that starts and ends in Aberystwyth and minimizes the distance that Santa must travel to deliver presents to all towns.

Merry Christmas!