Implementation of Dijkstra’s Shortest Path Algorithm in C++

Dijkstra’s Shortest Path Algorithm is popular algorithm for finding shortest path between different nodes. The algorithm (Pseudo Code) is as follows

Loading...

procedure Dijkstra (G): weighted connected simple graph,
with all weights positive)
[G has vertices a = v0, v1, ….. , vn = z and weights w(v1, v2)
where w(vi, vj) = INFINITY if [vi, vj] is not an edge in G]

for i := 1 to n
L(vi) := INFINITY
L(a) := 0
S := NULL
[ the labels are now initialized so that the label of a is 0
and all other labels are INIFINITY, S is empty set]
while z is not belongs to S
begin
u := a vertex not in S with L(u) minimal
S := S U [u]
for all vertices u not in S
If L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
[this adds a vertex to S with minimal label and updates the labels
vertices no in S]
end [L(z) = length of a shortest path from a to z]

Example:

Now lets come to an example which further illustrates above algorithm. Consider a weighted graph

DijkstraAlgorithm copy

 

Here a, b, c .. are nodes of the graph and the number between nodes are weights (distances) of the graph. Now we are going to find the shortest path between source (a) and remaining vertices. The adjacency matrix of the graph is

 

Dijkstra's Table

Now the following source code implements the above example

#include<iostream>
#define INFINITY 999
 
using namespace std;
 
class Dijkstra{
    private:
        int adjMatrix[15][15];
        int predecessor[15],distance[15];
        bool mark[15]; //keep track of visited node
        int source;
        int numOfVertices;
    public:
    /*
    * Function read() reads No of vertices, Adjacency Matrix and source
    * Matrix from the user. The number of vertices must be greather than
    * zero, all members of Adjacency Matrix must be postive as distances
    * are always positive. The source vertex must also be positive from 0
    * to noOfVertices - 1
 
    */
        void read();
 
    /*
    * Function initialize initializes all the data members at the begining of
    * the execution. The distance between source to source is zero and all other
    * distances between source and vertices are infinity. The mark is initialized
    * to false and predecessor is initialized to -1
    */
 
        void initialize();
 
    /*
    * Function getClosestUnmarkedNode returns the node which is nearest from the
    * Predecessor marked node. If the node is already marked as visited, then it search
    * for another node.
    */
 
        int getClosestUnmarkedNode();
    /*
    * Function calculateDistance calculates the minimum distances from the source node to
    * Other node.
    */
 
        void calculateDistance();
    /*
    * Function output prints the results
    */
 
        void output();
        void printPath(int);
};
 
 
void Dijkstra::read(){
    cout<<"Enter the number of vertices of the graph(should be > 0)\n";
    cin>>numOfVertices;
    while(numOfVertices <= 0) {
        cout<<"Enter the number of vertices of the graph(should be > 0)\n";
        cin>>numOfVertices;
    }
    cout<<"Enter the adjacency matrix for the graph\n";
    cout<<"To enter infinity enter "<<INFINITY<<endl;
    for(int i=0;i<numOfVertices;i++) {
        cout<<"Enter the (+ve)weights for the row "<<i<<endl;
        for(int j=0;j<numOfVertices;j++) {
            cin>>adjMatrix[i][j];
            while(adjMatrix[i][j]<0) {
                cout<<"Weights should be +ve. Enter the weight again\n";
                cin>>adjMatrix[i][j];
            }
        }
    }
    cout<<"Enter the source vertex\n";
    cin>>source;
    while((source<0) && (source>numOfVertices-1)) {
        cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;
        cout<<"Enter the source vertex again\n";
        cin>>source;
    }
}
 
 
void Dijkstra::initialize(){
    for(int i=0;i<numOfVertices;i++) {
        mark[i] = false;
        predecessor[i] = -1;
        distance[i] = INFINITY;
    }
    distance[source]= 0;
}
 
 
int Dijkstra::getClosestUnmarkedNode(){
    int minDistance = INFINITY;
    int closestUnmarkedNode;
    for(int i=0;i<numOfVertices;i++) {
        if((!mark[i]) && ( minDistance >= distance[i])) {
            minDistance = distance[i];
            closestUnmarkedNode = i;
        }
    }
    return closestUnmarkedNode;
}
 
 
void Dijkstra::calculateDistance(){
    initialize();
    int minDistance = INFINITY;
    int closestUnmarkedNode;
    int count = 0;
    while(count < numOfVertices) {
        closestUnmarkedNode = getClosestUnmarkedNode();
        mark[closestUnmarkedNode] = true;
        for(int i=0;i<numOfVertices;i++) {
            if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) {
                if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
                    distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
                    predecessor[i] = closestUnmarkedNode;
                }
            }
        }
        count++;
    }
}
 
 
void Dijkstra::printPath(int node){
    if(node == source)
        cout<<(char)(node + 97)<<"..";
    else if(predecessor[node] == -1)
        cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
    else {
        printPath(predecessor[node]);
        cout<<(char) (node + 97)<<"..";
    }
}
 
 
void Dijkstra::output(){
    for(int i=0;i<numOfVertices;i++) {
        if(i == source)
            cout<<(char)(source + 97)<<".."<<source;
        else
            printPath(i);
        cout<<"->"<<distance[i]<<endl;
    }
}
 
 
int main(){
    Dijkstra G;
    G.read();
    G.calculateDistance();
    G.output();
    return 0;
}

The output of above program is

DijkstraOutput

Loading...
SHARE Implementation of Dijkstra’s Shortest Path Algorithm in C++

You may also like...

39 Responses

  1. N Raz says:

    Thank you. Love the way you have put comments to explain as to what are you up too. Thank you and keep posting codes with comments. They really help

  2. Anonymous says:

    Great work. Clear, concise code. Thank you

  3. zawmyohtet says:

    Thank you.It helps me a lot.

  4. zawmyohtet says:

    May I asked you to post Bellman-Ford algorithm like this one.

  5. Ok i will post it after my exam :):)

  6. Thank You, but is it possible to get multiple shortest paths?

  7. Yep, there may be multiple shortest path between any two nodes. But above code only shows a single shortest path.

  8. How would you impliment this code by reading in a file formatted like this:
    1 2 10
    1 4 30
    1 5 100
    2 3 50
    2 1 70
    3 5 10
    3 1 50
    4 3 20
    4 5 60
    5 2 40
    Q

    the numbers (1-5) are the vertices and the third number in the line is the weight. the file length will be unspecified and Q terminates the file? Your code helps but im not sure how to convert to get this file format to work

  9. Anonymous says:

    Thanks ! great work and keep going, it was really helpful 😉

  10. Anonymous says:

    hey i am using turbo c and getting lot of errors in the program ..which one do you think is the best compiler to run this progam

  11. This code may not work in Turbo C. This is compiled using GCC MinGW Compiler.

  12. Anonymous says:

    thank you so much for your valuable reply Bibek..if you dont mind could you please tell me step by step instructions to run this program using GCC MinGW compiler. i am not able to do that please its a request

  13. Download the Code::Blocks binary from this link http://prdownload.berlios.de/codeblocks/codeblocks-12.11mingw-setup_user.exe. The GCC compiler is already embedded with this so just run the code and you will see the output

  14. Anonymous says:

    thank you so much!! everything is working fine 🙂 out of many other programs which i downloaded this is one giving the exact output as i wanted…happyyyyyyy:) 🙂

  15. Glad to hear that. This program actually uses Adjacency matrix. you can modify it to entire a entire graph instead of matrix. If you find any bug then let me know

  16. thanks for program . God bless you , should i prefer using priority queue instead ?

  17. Yes Rohit you can use priority queue. Priority queue makes the program even faster

  18. Preethi S says:

    Hi Bibek,

    I am trying to implement Dijkstra's algorithm in C with the help of your code above. I tried the same but somehow I am not able to get the expected shortest path.
    The modifications I have made are:
    Instead of asking user input for the number of nodes and cost, I am giving an input file which has all these info. I also mention the source and destination node from which I want the code to find the shortest path. But somehow everytime it just says no path from "source" to "destination"
    Will you be able to help me with this?
    Thanks in advance for any help.

    -Preethi

  19. Hello Preethi, please send me your code at [email protected]. I will look at it and provide you the feedback. Thanks

  20. Preethi S says:

    Hi Bibek,

    I have mailed you my source files. Please do have a look at it.
    Thanks

  21. Anonymous says:

    i am not able to run the above source code in dev c++ compiler.I got struck at line no 109.please help me

  22. Can you show me the error you got ?

  23. Anonymous says:

    Error:no'int Dijstra::getclosestUnmarkedNode()' member function declared in dijkstra
    In member function'void Dijkstra::calculate Distance()'

  24. Anonymous says:

    please help me to rectify this error

  25. pl providr source code for dijkstarts

  26. pl provide opengl source code for djkstarts

  27. bro there are errors of spaces there in the program
    press backspace and then tab then the errors will be corrected

  28. Nice and simple implementation. Nice job.
    But isn't the complexity n^2 instead of (m+n)logn?

  29. This algorithm is not dijkstra because no heap is maintained

  30. this would not work if it has a cycle. explain..d

  31. Thanks for the code! 🙂 could you explain how you would modify a graph to use this algorithm?

  32. can any one help me on find the shortest distance for all nodes by using Bellman-Ford algorithm cpp program

  33. hello can anyone help me with dis code?? getting a error with dis line bool mark[15]; pls anyone tell me

  34. hello can anyone help me pls?? getting a error in dis statement bool mark[15]; can anyone tell me pls

  35. can you show me link to bellman ford algorhytm

  36. Haider Ali says:

    Need Help!
    How can we get an alternate path using this algorithm?
    its Urgent.

  37. Anonymous says:

    Thank you for Dijkstra Code.

  38. Anonymous says:

    Ok bhai karta send….

  39. i can't understand ur code hell!

Leave a Reply

Your email address will not be published. Required fields are marked *

Share