Shortest Paths [40A]

Contributed by Francis Glassborow

Given the Cartesian co-ordinates of a number of points determine the shortest network of orthogonal paths (though there will be a shortest total, it will not always be a unique solution) that connect all the points. In the simplest form paths have to be parallel to the principle axes. If you are more ambitious you can allow rotation of the axes.

Note that this is a simplified version of a spanning-tree (sometimes called the Travelling Salesman Problem what is the shortest route so that a salesman can visit everyone of his customers?). The addition of the requirement that connections are constrained to a pair of orthogonal directions makes some aspects of the problem simpler (i.e. it is easier to compute distances).

If you want to further simplify the problem, constrain both the points and the paths to a unit grid.

Program elements

You need very few elements of a programming language. However you will probably need to explore the concept of back-tracking solutions. I.e. Get a solution and then try backing up a few steps to see if an alternative decision gives a better answer.

Hints

Before you start a program design try some simple cases with paper and pencil.

Extensions

Try it in three dimensions

Try adding the requirement that the total path length includes return to the starting point.