C++ program to solve the single source shortest path problem Using Dijkstra’s algorithm

/* Write a C++ program to solve the single source shortest path problem using Dijkstra’s algorithm */

#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
int shortest(int ,int);
int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p;
main()
{
int c;
cout <<"enter no of vertices";
cin >> n;
cout <<"enter no of edges"; 
cin >>m;
cout <<"\nenter\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin >> i >> j >>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
cout <<"enter initial vertex";
cin >>v;
cout << v<<"\n";
shortest(v,n);
 }
 
int shortest(int v,int n)
{
int min;
for(i=1;i<=n;i++)
{
S[i]=0;
dist[i]=cost[v][i];
}
path[++p]=v;
S[v]=1;
dist[v]=0;
for(i=2;i<=n-1;i++)
{
k=-1;
min=31999;
for(j=1;j<=n;j++)
{
if(dist[j]<min && S[j]!=1)
{
min=dist[j];
k=j;
} 
}
if(cost[v][k]<=dist[k])
p=1;
path[++p]=k;
for(j=1;j<=p;j++)
cout<<path[j];
cout <<"\n";
//cout <<k;
S[k]=1;
for(j=1;j<=n;j++)
if(cost[k][j]!=31999 && dist[j]>=dist[k]+cost[k][j] && S[j]!=1)
 dist[j]=dist[k]+cost[k][j];
}
}

OUTPUT

enter no of vertices6
enter no of edges11

enter
EDGE Cost
1 2 50
1 3 45
1 4 10
2 3 10
2 4 15
3 5 30
4 1 10
4 5 15
5 2 20
5 3 35
6 5 3
enter initial vertex1
1
14
145
1452
13

11 Responses to “C++ program to solve the single source shortest path problem Using Dijkstra’s algorithm”

CapnCrax November 30, 2010

learn to comment and tab your code noob! shouldn’t have to spend that long checking through your process.
usman June 16, 2011

Awsome man…simplest , no fkin classes/library ftns; yet very effective and better and easy to understand……..yup this program is 8/10
Nassary September 7, 2011

Your program so simple i wish all the best
Nassary September 7, 2011

May this program can be eloborated more so as to be well definable to any one who did not able to realise the piece of codes used
lovejit October 13, 2011

#include
#include
int dist[20];
int search(int n1,int s[],int dist[]);
void dijkestra(int n1,int v,int c[20][20]);
int main()
{
clrscr();
cout<<"enter the no of vertices:"<>n1;
cout<<"enter the source vertex:"<>v;
cout<<"enter the no of edges:"<>n2;
int a,b,d,i,j;
int e[20][2],c[20][20],ch[20][20];
for(i=1;i<=n2;i++)
{
cout<<"enter the vertces and cost of "<<i<<"edge:"<>a>>b>>d;
e[i][1]=a;
e[i][2]=b;
c[a][b]=d;
ch[a][b]=1;
}
for(i=1;i<=n1;i++)
{
for(j=1;j<=n1;j++)
{
if(ch[i][j]!=1)
{
c[i][j]=30000;
}
}
}
dijkestra(n1,v,c);
cout<<"\nThe shortest path of source vertex "<<v<<"from:"<<endl;
for(i=1;i<=n1;i++)
{
cout<<"vertex "<<i<<"is:"<<dist[i]<<endl;
}
getch();
return 0;
}

void dijkestra(int n1,int v,int c[20][20])
{
int s[20];
for(int i=1;i<=n1;i++)
{
s[i]=0;
dist[i]=c[v][i];
}
s[v]=1;
dist[v]=0;
for(i=2;i<=n1;i++)
{
int u=search(n1,s,dist);
s[u]=1;
for(int j=1;jdist[u]+c[u][j])
{
dist[j]=dist[u]+c[u][j];
}
}
}
}

int search(int n1,int s[],int dist[])
{
int k,min;
for(int i=1;i<=n1;i++)
{
if(s[i]==0)
{
k=i;
min=dist[i];
break;
}
}
for(i=k+1;i<=n1;i++)
{
if(s[i]==0 && dist[i]<min)
{
k=i;
min=dist[i];
}
}
return(k);
}
Ankit jain April 30, 2012

this program is not right bcz it is noy runnnig and provids wrong output.
Neha nayak May 2, 2012

nice program,but some mistake in this program.
1.it provides the wrong output.
2. In the 2nd program symbole of “cout “&”cin”are wrong.
anand August 13, 2012

wrong program !!!
ankita August 22, 2012

boringgggggggggggggggggggggg!!!!!!!!!!!!!!!!!!!!!!!
sameer patil August 23, 2012

zop
Akash July 10, 2013

it doesn’t give paths to all the other vertices , one vertex does not get mentioned in output , help