I previously talked about a particular instance of the vehicle routing problem for electric vehicles in a post which you can read here.
In fact that was a more challenging version of a classic problem in combinatorial optimisation – finding an optimal path. So it would be remiss of me if I didn’t go right back to the start: Dijkstra’s algorithm.
Dijkstra’s algorithm is designed to find to find the shortest path between two points in a graph and does exactly that. It is a systematic approach that was devised by Edsger W. Dijkstra in 1956 and has been widely used since. The main application of it that you’ve come across is probably the use of it to find optimal routes for vehicles in road networks.
The truly usefulness is that it can be performed on computers, which mean that optimal paths can be found through larger and more complicated networks than it is possible to do by hand. Although nowadays even better algorithms have been developed to determine the best route that you use in your satnav, speed is of the essence here nobody wants to be waiting for ages for the route to be computed, they were all built upon the foundations laid by Dijkstra’s algorithm.
Steps to Djikstra’s Algorithm
- Label the starting vertex as 0 and select it as the current vertex.
- For every uncompleted vertex that is connected to the current vertex:
- Calculate: current vertex + edge connecting it to current vertex
- If this is less than the current label or if there isn’t a label, it becomes the new label
- Label current vertex as completed
- Select the uncompleted vertex with smallest label as the new current node.
- Repeat steps 2-4 until the destination vertex is labelled.
Then we see that that the label on the destination vertex will be the length of the shortest path. We can find the location of the shortest path by working backwards from the destination vertex.
If vertex Y lies on the path, then vertex X is the previous vertex if,
label at Y – label at X = edge XY
We can then repeat this until we trace the path back to the start.
Example
As with most things this is usually easiest to see with an example. Below is a simple example I created with 7 nodes that uses Dijkstra’s algorithm to find the shortest path from G to A.
The grey circles represent uncompleted vertices, blue circles completed vertices and the red circle illustrates the current vertex.
