# 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

*/

/*

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
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 predecessor[15],distance[15];
bool mark[15];
int source;
int numOfVertices;
public:
void initialize();
int getClosestUnmarkedNode();
void dijkstra();
void output();
void printPath(int);
};

{
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;
}

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++) {
cout<<“Weights should be +ve. Enter the weight again\n”;
}
}
}

//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++) {
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.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

*/

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

1. jyothi says:

Thank you very much. This example is been a great help for my test.

2. Ferhat says:

Where can i find codes for Dijkstra and Bellman-Ford Algorithms in C++ or VisualC like this example?? Please help me!! Thanks.
ferhatkarakoyun@hotmail.com

3. samar shah says:

good effort i will try it

4. ^_^ says:

thank you very much

5. Ashutosh says:

Thanks a lot!! Really helps!!

6. Eros says:

Thank you!

7. QQ Tan says:

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

8. urgent says:

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..

9. Can you send this code in my e-mail please? I’m not able to see all the code here…Tks

10. shashi ranjan singh says:

i want to know the programming for shortest path using dijstra’s floyd’s algorithm

11. it not executing properly …..

12. ali says:

how can i use this code

i can run but i don’t understand

13. one of ur friend says:

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

14. 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 :).

15. salar says:

pleas write Code For Dijkstra’s Algorithm In C#

16. The code is good I got it and it is so simple

17. DIANA says:

thank u !!!!!!!!!!!!!!!!!

18. ashok says:

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#######

19. ramesh naik says:

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

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

20. hi says:

hi is this program working 100% accurately????????

looking forward for an immediate help

thank you

21. 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

22. 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

23. xristina says:

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 !

24. preethi says:

thank u

1. chini says:

wah sweety………….,.

25. chini says:

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………

r u talking abt distance[ source ] =0

1. Kimon says:

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.

26. Rho says:

Thanx a lot !!! 🙂 🙂 Was searching for it !!! 🙂

27. yasser says:

Thanks

28. jithin says:

great it helps alot

29. jerome says:

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

30. gamebak says:

Thanks man for this solution, but i didn’t get the last part when introducing the source vertex

31. 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

32. king says:

thanks sir it really very helpfull for me……..

33. newbie says:

what does this mean?
————
distance

[/source]

= 0;

34. sachin says:

i think its to large

35. sunaina says:

looking Easy to understand.Thank You.

36. lameck andrew says:

thanks man that code right there works good!!!