# Implementation of Dijkstra Algorithm in C++

```#include<iostream.h>
#include<conio.h>

void main()
{
int i, j;

//Get vertex numbers
int vn;
cout<<"\n Enter vertex count: ";
cin>>vn;

//Cost matrix
int cost[15][15];
for (i=0;i<vn;i++)
{
for(j=0;j<vn;j++)
{
cost[i][j]=-1;
}
}

//Get cost matrix
cout<<"\n Enter weight of edge:\n";
for(i=0;i<vn;i++)
{
for(j=0;j<vn;j++)
{
if(i==j)
cost[i][j]=0;

if(cost[i][j]==-1)
{
cout<<"\n "<<i<<" to "<<j<<" : ";
cin>>cost[i][j];
}
}
}

//Displaying cost matrix
cout<<"\n Entered Cost Matrix:";
cout<<"\n";
for(i=0;i<vn;i++)
{
for(j=0;j<vn;j++)
{
cout<<cost[i][j]<<" ";
}
cout<<"\n";
}

//Initializing single source
int d[15], p[15], f[15];
for(i=0;i<vn;i++)
{
d[i]=999;	//distance	->	infinity
p[i]=-1;	//parent	->	null
f[i]=0;		//visited	->	no
}

//Get starting vertex
cout<<"\n Enter Starting vertex: ";
int s;
cin>>s;

//Process staring vertex
d[s]=0;
p[s]=-1;
f[s]=1;

int c=s;
int temp1;
int smallest=999;

for(i=0;i<5;i++)
{
//update distances
for(j=0;j<vn;j++)
{
if(cost[j]>0)	//Check if edge is present
{
if(d[j]>d+cost[j])
{
d[j]=d+cost[j];
p[j]=c;
}

}
}

//Mark vertex visited
f=1;
smallest=999;

//Retrieve smallest vertex from remaining
for (int k=0;k<vn;k++)
{
if(f[k]!=1 && d[k]<smallest)
{
smallest=d[k];
c=k;
}
}

smallest=999;

}

//Display result
cout<<"\n Shortest Path:";
cout<<"\n Vertex\tDist\tParent\n";
for(i=0;i<vn;i++)
{
cout<<i<<"\t"<<d[i]<<"\t"<<p[i]<<"\n";
}

getch();
}

/* OUTPUT

Enter vertex count: 5

Enter weight of edge:

0 to 1 : 10

0 to 2 : -1

0 to 3 : 5

0 to 4 : -1

1 to 0 : -1

1 to 2 : 1

1 to 3 : 2

1 to 4 : -1

2 to 0 : -1

2 to 1 : -1

2 to 3 : -1

2 to 4 : 4

3 to 0 : -1

3 to 1 : 3

3 to 2 : 9

3 to 4 : 2

4 to 0 : -1

4 to 1 : -1

4 to 2 : 6

4 to 3 : -1

Entered Cost Matrix:
0 10 -1 5 -1
-1 0 1 2 -1
-1 -1 0 -1 4
-1 3 9 0 2
-1 -1 6 -1 0

Enter Starting vertex: 0

Shortest Path:
Vertex Dist    Parent
0       0       -1
1       8       3
2       9       1
3       5       0
4       7       3

*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.