More

    [ALGORITHM] DIJKSTRA’S ALGORITHM FOR FINDING SHORTEST PATH FOR A GRAPH

    Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra, is a graph search algorithm that finds shortest path to every element from a source element in a graph with non-negative edge path costs, producing a shortest path tree.

    In a graph, there will be some vertices and there will be edges between those vertices; and in a weighted graph, there will be weights for each edge, written over those edges as below. In this diagram, A, B, C, D, E, F, G are the vertices. The weight (edge path cost) on the edge (line between vertices) between A and B is 2, A and D is 4 and so on.

    Our aim is to find the shortest distance from a source to all elements, and also the path. For every element we find the previous element through which it can be reached through the shortest path from the source. Once we connect the previous elements and reach source, we get the shortest path to that element from the source.

    Let us understand with an example. First we will see the final output and then see how we can derive on that using Dijkstra’s algorithm. For the above graph with source as A, the final shortest distance and path (previous node in shortest path) will be as below (Vertex-Distance-Previous):

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-3-C
    • E-5-B
    • F-7-D
    • G-6-E

    Here, distance (second column) is the final shortest distance from any vertex till the source (A) when you take the path through the previous node (path). From this table, we can see that the final shortest distance from G to the source (A) will be 6 and we can find the shortest path from G to A (source) as G-E-B-A. First we can draw an edge from G to E as E is the previous node for G in the above table. Then we can draw an edge from E to B as B is the previous node for E in the above table. Then we can draw an edge from B to A as A is the previous node for B in the above table. If we calculate the sum of all edge costs from G to A in this path, it will be 6. Next we will see how we derived it from the graph.

    Using Dijkstra’s algorithm to get the above output

    We should use some data structure to store vertices, their distances and previous node in shortest path as above. We also need a PriorityQueue. A queue is a first in first out data structure where the first elements inserted will the first elements taken out. However in a PriorityQueue, elements are taken out based on their priority.

    First we will initialize the source node (A) distance (distance to itself) as 0 and all non-source distance to -1, and all path (previous node in shortest path) as null or blank. We will also insert the source node A with its priority as its distance 0 into the priority queue.  Therefore, the initial Node-Distance-Path table is:

    • A-0-NA (No path applicable as this is the source.)
    • B-(-1)-
    • C-(-1)-
    • D-(-1)-
    • E-(-1)-
    • F-(-1)-
    • G-(-1)-

    Initial Priority Queue is: A (0). The priority (distance) is given in the braces.

    We will iterate over this initial table and stop the iteration if the priority queue is empty after any iteration. In each of the iterations, we will select the vertex with maximum priority (minimum distance) from the priority queue. For each edge connected to it, we will calculate the distance to reach that edge through the selected vertex. If the calculated new distance is smaller than the one in the distance table, we will replace the one in distance table with the new one. If the distance table is having -1, we will simply replace it with the new distance without any comparison.  We will first see the pseudo code, and then the result of each of the iterations with the above example to make things clear. Note that pseudo code is not any language specific, though it is very close to java here.  

    Pseudo Code for Dijkstra’s algorithm:

    /* PQ is the priority queue. Weight[a][b] contains the path cost from a to b in the graph for any a, b. Distance[i] contain the distance of i to source after each iteration. Path[i] contains the previous node of i in the shortest path to source after each iteration.*/

    void Dijkstra(Graph G, int source){

          PriorityQueue pq=new PriorityQueue();

             int v, w;

             pq.enQueue(source);

          for(int i=0;i<G.vertexCount;i++)

            {        

              distance[i]=-1;

            }

             distance[source]=0;

          while(!pq.isEmpty()){

                  v=pq.getAndDeleteVertexWithMinDist();

                  for all adjacent vertices w of v{

                           Compute new distance d=distance[v]+weight[v][w];

                           if(distance[w]==-1){

                                      distance[w]=d;

                                   Insert w in the pq with priority d

                                      path[w]=v;

                           }

                              else if(distance[w]> d){

                                      distance[w]=d;

                                   Update priority of vertex w to be d;

                                      path[w]=v;

                           }

                  }

          }

    }

    Now take a pen and paper and try it out along with me. After one or two iterations along with me, try to do it yourself and compare it with the results here. If you are stuck, you can do it along with me and still stuck or confused, you can ping me or call me.

    Initial table

    • A-0-NA (No path applicable as this is the source.)
    • B-(-1)-
    • C-(-1)-
    • D-(-1)-
    • E-(-1)-
    • F-(-1)-
    • G-(-1)-

    Added A (0) to PQ. PQ now contains A (0).

    Iteration 1: Select A (0) from PQ as it is the only one now.

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-4-A
    • E-(-1)-
    • F-(-1)-
    • G-(-1)-

    Added B(2), C(1), D(4) to PQ. PQ now contains B(2), C(1), D(4)

    Iteration 2: Select C (1) from PQ as it is the one with maximum priority (minimum distance)

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-3-C
    • E-6-C
    • F-8-C
    • G-(-1)-

    Added E(6), F(8) to PQ. Updated D(4) to D(3). PQ now contains B(2), D(3), E(6), F(8)

    Iteration 3: Select B (2) from PQ

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-3-C
    • E-5-B
    • F-8-C
    • G-(-1)-

    Updated E(6) to E(5) in PQ. PQ now contains D(3), E(5), F(8)

    Iteration 4: Select D(3) from PQ

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-3-C
    • E-5-B
    • F-7-D
    • G-(-1)-

    Updated F(8) to F(7) in PQ. PQ now contains E(5), F(7)

    Iteration 5: Select E(5) from PQ

    • A-0-NA (No path applicable as this is the source.)
    • B-2-A
    • C-1-A
    • D-3-C
    • E-5-B
    • F-7-D
    • G-6-E

    Added G(6) to PQ. Current PQ contains F(7), G(6)

    G and F don’t have any shortest path through them. So Iteration 5 is the final answer.

    Every time you learn an algorithm like this, the best approach to understand it is to try it out using a pen and paper like below. Take a sample input; go through each step and iteration writing down all variable values. After each of the iterations, you will understand more and more.

    TODO: understand the algorithm well and try to write the program yourself.

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox