Dijkstra’s Algorithm

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.

mapDijkstra’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

  1. Label the starting vertex as 0 and select it as the current vertex.
  2. For every uncompleted vertex that is connected to the current vertex:
    1. Calculate: current vertex + edge connecting it to current vertex
    2. If this is less than the current label or if there isn’t a label, it becomes the new label
  3. Label current vertex as completed
  4. Select the uncompleted vertex with smallest label as the new current node.
  5. 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.

This slideshow requires JavaScript.

The grey circles represent uncompleted vertices, blue circles completed vertices and the red circle illustrates the current vertex.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s