Code For Dijkstra’s Algorithm In C++


/*

Note: Because of encoding problems the following code may not work. If it doesn’t work download the code from the following link. Right click on the link and click on ‘save target as ‘ and save the text file

Download the code:   dijkstra.txt

*/

/*

Title: Dijkstra’s single source shortest path algorithm
Author: Vinodh Kumar B

Description:
adjMatric[][] : This array is used to store the adjacency matrix of the input graph
predecessor[] : This array is used to store the predecessor elements. predecessor[i] is the previous element in the path from source to current node i.
ex: If 1->2->4->3 is the shortest path from node1(source) to node 3. predecessor[3] is 4.
distance[]      : This array will store the minimum distance from the source to corresponding node. It will be updated in each iteration in dijkstra’s                     algorithm.
mark[]          — This array is used to mark the nodes as visited. mark[i] = true, This means node i is marked as visited.
source          — source is the starting node from which we have to find out the shortest distance to all other nodes in the graph.
numOfVertices — The number of nodes in the graph.
Note: Node ranges will be 0 to numOfVertices-1

getClosestUnmarkedNode()    : This method will return the closest unmarked node from the current marked node.
printPath(i)                : This will print the path from source node to i in recursive manner
output()                    : This method will print paths to all nodes from source and their shortest distance
read()                        : This method will read the graph values from input
initialize()                : This method will set the initial values of predecessor[] to -1 and
dijkstra()                    : This method will implement the dijkstra’s algorithm

*/

#include<iostream>
#define INFINITY 999
using namespace std;

class Graph
{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
bool mark[15];
int source;
int numOfVertices;
public:
void read();
void initialize();
int getClosestUnmarkedNode();
void dijkstra();
void output();
void printPath(int);
};

void Graph::read()
{
cout<<“Enter the number of vertices of the graph(should be > 0)\n”;
cin>>numOfVertices;
//Number of vertices should always greater than zero
while(numOfVertices <= 0) {
cout<<“Enter the number of vertices of the graph(should be > 0)\n”;
cin>>numOfVertices;
}

//Read the adjacency matrix for the graph with +ve weights
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];
}
}
}

//read the source node from which the shortest paths to other nodes has to be found
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 Graph::initialize()
{
for(int i=0;i<numOfVertices;i++) {
mark[i] = false;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance

[/source]

= 0;
}

int Graph::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 Graph::dijkstra()
{
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 Graph::printPath(int node)
{
if(node == source)
cout<<node<<“..”;
else if(predecessor[node] == -1)
cout<<“No path from “<<source<<“to “<<node<<endl;
else {
printPath(predecessor[node]);
cout<<node<<“..”;
}
}

void Graph::output()
{
for(int i=0;i<numOfVertices;i++) {
if(i == source)
cout<<source<<“..”<<source;
else
printPath(i);

cout<<“->”<<distance[i]<<endl;
}
}

int main()
{
Graph G;
G.read();
G.dijkstra();
G.output();
return 0;
}

/*Sample output:

[vinod@thelegendbox cpp]$ g++ dijkstra.cpp
[vinod@thelegendbox cpp]$ ./a.out
Enter the number of vertices of the graph(should be > 0)
5
Enter the adjacency matrix for the graph
To enter infinity enter 999
Enter the (+ve)weights for the row 0
0
2
4
999
1
Enter the (+ve)weights for the row 1
2
0
7
3
999
Enter the (+ve)weights for the row 2
4
7
0
2
999
Enter the (+ve)weights for the row 3
999
3
2
0
6
Enter the (+ve)weights for the row 4
1
999
999
6
0
Enter the source vertex
0
0..0->0
0..1..->2
0..2..->4
0..1..3..->5
0..4..->1

*/

43 thoughts on “Code For Dijkstra’s Algorithm In C++”

  1. Function Dijkstra(L[1..n, 1..n]): array [2..n] array D[2..n], P[2..n] C = {2, 3, …, n} for i = 2 to n do D[i] = L[1, i] P[i] = 1 repeat n – 2 times v = the index of the minimum D[v] not yet selected remove v from C // and implicitly add v to S for each w Î C do if (D[w] > D[v] + L[v, w]) then D[w] = D[v] + L[v, w] P[w] = v return D, P

    //can convert this pseudocode for me by today 24/08/07???thanks u so much

  2. pls make another program that will require the user to input exit node…. thank you poh!!! it helps us a lot in our case study…we need it before October 19.,can you pls make us a program?plsss..

  3. hi;u have a nice site…
    would u plz write a prog abt dfs and bfs traversal in graph with c++….i really need it as soon as possible

  4. Wow, for someone who has gone out of their way to post some nice code (thanks btw.) there sure are a lot of demanding people posting their “needs.” Aside from looking like kid trying to get someone else to do their work for them I humm… no sadly that’s what all these comments look like, aside from the odd thanks in there🙂.

  5. can you give me a some short of information about dijkstra
    what is the application of dijkstra ?
    plz email this information to me.
    thank you very much in advance.

    #########ashok rathod#######

  6. Implement modified Dijkstra’s shortest paths algorithm that also gives the count of number of shortest paths to every node.

    Input: The weighted (positive weights) directed graph
    with node 1 considered as source is taken as input from a file the first line
    having the size of the graph to be read (the size of the graph is dynamically set)

    The file format:

    n
    adjacency matrix of size n

    Output: The shortest paths from source to every node has to be printed along with the count of paths at that node.

  7. Hi, Vikram
    I really liked your blog very helpful and full of knowledge on different programming languages.

    This program on Dijkstra is working fine on my machine, now the question is that can i implement “dijkstra algorithm of shortest path” in socket programming for routers.

    Suppose there are 6 no. of routers and i want to send a data packet from source router to another.

    Looking forward to hear from you.

    Javed Akhtar

  8. Hi, Vinod (apology for the wrong name in the previous comment)
    I really liked your blog very helpful and full of knowledge on different programming languages.

    This program on Dijkstra is working fine on my machine, now the question is that can i implement “dijkstra algorithm of shortest path” in socket programming for routers.

    Suppose there are 6 no. of routers and i want to send a data packet from source router to another.

    Looking forward to hear from you.

    Javed Akhtar

    Reply

  9. Hi can you please explain what exactly is the source vertex?
    ANd i would like to ask if you could help me to find a shortest path with specific nodes and vertex but with random weight for those that have weight !
    Please email to me !

  10. what to do for distances on line 69 where distance=0?
    how can be a distance array intialized like distance=0????????????
    it’s gives error for that reply soon………….
    ha but very useful prg……
    in lab sessions………

      1. Vinod can you please upload the .txt file again? I have the encoding problem and the link to download the .txt does not work so I’m guessing you took it down.
        ~thanks in advance

  11. hi dude it does not work
    what to do for distances on line 69 where distance=0?
    how can be a distance array intialized like distance=0

  12. Thanks in advance Vinod this was a huge help in my TSP assignment I’ve credited you for the implementation and I’ll modify it for my solutions.

    Traveling Salesman Problem

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