Fundamentals of algorithmsː Optimisation algorithms

4.3.6 Optimisation algorithms

Understand and be able to trace Dijkstra’s shortest path algorithm. Be aware of applications of shortest path algorithm.

Students will not be expected to recall the steps in Dijkstra's shortest path algorithm.

Dijkstra's Shortest Path

Dijkstra was a Dutch computer scientist who created the shortest path algorithm. It took him 20 minutes apparently.

One of the many features of a smart phone is the fact that they can generate routes between different places quickly. The criteria for selection varies from fastest or shortest and often can involve walking, cycling, driving or public transport. If you divert from your original path the phone will reroute you, often in seconds. One method of finding the optimal route efficiently is by using Dijkstra's algorithm. This is an example of an optimisation algorithm.

What does Dijkstra's algorithm do?

There are many linked locations on a map, start at any one of them and find the shortest distance to get to another one. All the locations are linked together via intermediate locations and the time of travel between any two linked locations is known. However, not all locations are linked directly.

Lets look at Dikstra's solution by creating an abstraction of a map.

....... Diagram of a map here ........

First the we need to create a map of the locations. We call the locations nodes.

....... diagram of nodes ......

The distance (or times depending on the problem) between and two nodes is called a vertex (plural vertices).

...... diagram of nodes and vertices .....

So how can we create an algorithm based on this information to efficiently work out the shortest distance?

First the abstraction is created and the nodes and labeled vertices are added as shown above. The starting node is then identified. Each node which is directly linked to the starting node is identified and the distance from the staring node assigned to it. (These are the numbers which are written in the circles representing the node in the linked example below) The vertices are all coloured green. Green vertices might be part of the shortest route.

Next, the node containing the smallest number is identified. The nodes linked to this node are identified and the total of the vertices from the starting point to these new nodes are calculated (and written in the node) If one of these nodes already has a value in it which is higher the newly calculated number then it is crossed off and replaced with the smaller number. The vertex which has been added to the node is coloured green. If one of these nodes has a value in it which is lower or equal to the newly calculated number then it is ignored.

This process is then repeated. ie The new smallest node is identified and all the directly the linked nodes are identified and the total distances are calculated. Vertices which are part of the new shortest distance are coloured green. Eventually the node with the shortest value in it is the node that we are trying to reach. The value in it is the shortest distance between the start node and the terminating node.

The path that links them is the green path between them

This animation will help you to see the process.

http://www.gitta.info/Accessibiliti/en/html/Dijkstra_learningObject2.html

While Dijkstra's algorithm is designed to find the shortest distance between two points the final network has the shortest distance from the starting point to any point in the network.

If the network on the animation had another node which was further than 12 units from the start node it clearly is not involved with the shortest path but the algorithm will run until all possible nodes and paths have been considered. If this issue went unresolved in a Sat Nav it would be considering roads in Scotland before finding the best route from London to Birmingham.This is clearly a waste of time. A straight forward refinement to Dijkstra's algorithm would be to have it stop once all unconsidered vertices were equal or greater than the shortest distance calculated between the starting point and the desired finishing point.