Shortest Path Algorithm: Dijkstra algorithm

Quote of the day: Simplicity is prerequisite for reliability.

 

I previously touched upon the shortest path problem which in summary is a problem involving finding shortest distance between nodes in a graph, provided that the distance between adjacent nodes exists and expressed in numbers. The problem is among many different graph problems defined in Computer Science and there are several algorithms or solutions provided to the shortest path problem.

 

In this article, I am going to look at a particular algorithm or solution called the Dijkstra algorithm (one of my favourite algorithms) by Edsger Wybe Dijkstra.

 

Pseudocode

The Dijkstra algorithm is detailed below in a format called a Pseudocode:

Given a graph such as the image above, and a node could be node 0, we follow these steps

  1. Define a set of nodes which we call Q
  2. For each node in the graph do the following:
    1. Initialize the array of distance with all values being infinity
    2. Initialize the adjacent array with unknown
    3. Add the node to the set Q
  3. Set distance from source to itself to be 0.
  4. While our set Q is not empty repeat the following:
    1. Select a node in Q with the minimum distance from source to that node. Call that node U.
    2. Delete that node U from set Q
    3. For each of the neighboring nodes of node U do the following:
      1. Calculate the distance to reach the node U from its neighbor node S. now let alt = distance[U] + length(u,v)
      2. If alt is less than distance[S] then set distance[S] = alt and previous[S] = U
  5. Return distance and previous arrays

 

Below is a quick video demonstrating how the algorithm works using an example:

 

Thank you for reading and watching.