AutoSnail
This program, taken from a first year practical at Oxford, finds the shortest driving route between two towns. For this demonstration, only a small number of towns in Britain are shown. In the practical, students analyse and improve the efficiency of the program when it is used with much larger networks of towns and roads.
Instructions
Use the mouse on select two towns: a starting town (which will light up in green) and a finishing town (which will light up in red). Press the Search button to find the shortest route between them.
Click on the checkbox labelled 'Show working' to view the calculations done by the program as it searches. Roads are coloured blue if they are known to be on the shortest route from the start to some other town. A town is coloured white if the shortest route to that town has been found.
The program works by considering roads (shown in green) that link a white town to another town that is still black. It chooses the closest such town, colours it white, and colours the road that reaches it blue. Some other roads may now be coloured green. This process continues until the destination town is coloured white, at which point the program shows the shortest route in yellow. It's possible to prove mathematically that this program does always give the correct result, and within a guaranteed time.
The magenta roads are ones that were once green, but were never selected to be coloured blue – the fact that such roads exist shows that other, less careful, methods would sometimes give the wrong answer. For example, a program that just chose the road that took us closest to the destination could get stuck in a dead end. And a program that tried every possible route would take far too long.
By selecting the switch labelled 'Delay between steps', you can slow the program down to watch it at work. The switch labelled 'Use heuristic' biases the search in favour of roads that go roughly the right way, making the search more efficient.