# CODE-2 FOR DIJKSTRA’S SHORTEST PATH ALGORITHM IN C++

/*************************************************************************

-> This C++ program is to implement Dijkstra’s algorithm for
single source shortest path problem

-> This program works in Microsoft VC++ environment in windows xp

-> Data structures used:

1)iostream.h
2)stdlib.h

/*************************************************************************/
#include<iostream.h>
#include<stdlib.h>

#define MAX 20
#define INFINITY 9999

class dijkstra
{
private:
int n;
int graph[MAX][MAX];
int colour[MAX];
int start;
int distance[MAX];
int predecessor[MAX];
enum {green,yellow,red};
public:
void initialize();
int select_min_distance_lable();
void update(int);
void output();
void function();
};

{
cout<<“Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<“Enter the adjacency matrix for the graph ::\n”;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>graph[i][j];
for(i=1;i<=n;i++)
colour[i]=green;

cout<<“Enter the start vertex ::”;
cin>>start;
}

void dijkstra::initialize()
{
for(int i=1;i<=n;i++)
{
if(i==start)
distance[i]=0;
else
distance[i]=INFINITY;
}

for(int j=1;j<=n;j++)
{
if(graph[start][j]!=0)
predecessor[j]=start;
else
predecessor[j]=0;
}
}

int dijkstra::select_min_distance_lable()
{
int min=INFINITY;
int p=0;
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(min>=distance[i])
{
min=distance[i];
p=i;
}
}
}
return  p;
}

void dijkstra::update(int p)       // p is a yellow colour node
{
cout<<“\nupdated distances are ::\n”;
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(graph[p][i]!=0)
{
if(distance[i]>graph[p][i]+distance[p])
{
distance[i]=graph[p][i]+distance[p];
predecessor[i]=p;
}
}
}
cout<<distance[i]<<‘\t’;
}
}

void dijkstra::output()
{
cout<<“****** The final paths and the distacnes are ******\n\n”;

for(int i=1;i<=n;i++)
{
if(predecessor[i]==0 && i!=start)
{
cout<<“path does not exists between “<<i<<” and the start vertex ”
<<start<<endl;
exit(1);
}
cout<<“path for node “<<i<<” is ::\n”;
int j=i;
int array[MAX];
int l=0;
while(predecessor[j]!=0)
{
array[++l]=predecessor[j];
j=predecessor[j];
}
for(int k=l;k>=1;k–)
cout<<array[k]<<“->”;

cout<<i<<endl;
cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
}
}

void dijkstra::function()
{
cout<<“\n**********************************************************************\n”;
cout<<“This program is to implement dijkstra’s algorithm using colour codes \n”;
cout<<“**********************************************************************\n\n”;
initialize();
//repeate until all nodes become red
int flag=0;
int i;

cout<<“\n\n******** The working of the algorithm is **********\n\n”;

for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;

cout<<“The initial distances are ::\n”;
for(i=1;i<=n;i++)
cout<<distance[i]<<‘\t’;
cout<<endl;

while(flag)
{
int p=select_min_distance_lable();
cout<<“\nThe min distance lable that is coloured yellow is “<<p;
colour[p]=yellow;

update(p);
cout<<“\nnode “<<p<<” is coloured red “<<endl;
colour[p]=red;

flag=0;
for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;

cout<<endl<<endl<<endl;
}
output();
}

void main()
{
dijkstra d;
d.function();
}

## 29 thoughts on “CODE-2 FOR DIJKSTRA’S SHORTEST PATH ALGORITHM IN C++”

1. Ferhat says:

2. THANKS
WE are expecting suggestions from u to improve the blog and to make it to be useful for a large no.of people

3. puppis says:

Thank you, thank you, thank you for Dijkstra’s algorithm you’ve done!

4. sunil says:

HI THANK YOU FOR THE CODE ,, IT IS VERY USEFUL.

can u pl also give an code for generating adjacency matrix .
thanx
sunil.

5. sai says:

hey can u tell me whether this program gves info abt the value of the quickest path and sequence of nodes on the quickest path(i mean o/p..)

6. sunny says:

thanx for the code….. but if i want to write the Dijkstra’s code for a large no. of cities then i think this code wont work….. in that case we have to use database….. if so then how?

7. sameer says:

plz type in the proper comments in the program

8. Sindhuja says:

Excellent code.
Dijkstra’s will giv the shortest path from only one source vertex to all other vertices.but, why not u try for all-pairs? Like, Can u code for Floyd’s, Dantzig’s and double-sweep all-pairs algorithm? if so, it’ll be of very help to me.

9. M Sufian Tarar says:

it is not working
i give the adjacency matrix and the start vertex and after that the program simply starts running and never ends leaving my pc stuck
what is it worth ???
!!

10. lakshmi says:

Hi,
can you plz send me a code for the implementation of Dijkstra’s Algorithm using linked list

11. sanjay goswami says:

pl give the code using Adjacency list

12. San says:

Hi All,
Dijkstra’s will giv the shortest path from only one source vertex to all other vertices.but, how to find out the shortest path from one source vertext to one destination vertex. i.e., Dijkstra shortest path algorithm for one to one.

13. i think the program is bad one…
because i’m not understand and the prog without validation
omg it’s terriebel

14. Victor says:

Dear Vinod,
Can you example DIJKSTRA’S SHORTEST PATH ALGORITHM IN C. Because C and C++ is more different. I hope you sent my mail(keepwalking_ht@yahoo.com).
Thank Vinod very much.
Best and Regards !!!

15. ALI says:

THANK YOU BUT I NEED THE CODE IN MATLAB CAN YOU GIVE ME THIS..PLZ..

16. Hi,
Can you give me the code to implement two stacks using a single array in c++.?

17. vandana says:

nice job thank u 4 ur code
it helped a lot in our labs

18. wonde says:

thank u. it’s very useful.

19. Shailendra says:

hiiii…
Thanks for the illustrative Algoritm.
Thanks a lot….. 🙂

20. siri says:

hi can u help me to write dijkshtras program in c++. and the above program running accurately. plz mail me to this id .
shirisha152002@yahoo.co.in

21. siri says:

hi its very urgent and i m looking for help

22. mamal says:

Thanks a lot!! I really appreciate! nice code.

23. prakash.a says:

any one please send the maximum bandwidth location heuristic algorithm in c++…

24. Barkın Bora says:

Sikini taşşağını yiyim senin be ! Koçum benim !

25. Lokesh Gagnani says:

what to enter for Adjacency matrix as 0 gives error & -1 negative nos error?

26. this one is very largest one……………….give me some simplest one………….

27. It’s amazing in support of me to have a web page, which is good in favor of my