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

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

  1. learn to comment and tab your code noob! shouldn’t have to spend that long checking through your process.

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

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

    Reply
  4. #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);
    }

    Reply
  5. Ankit jain

    this program is not right bcz it is noy runnnig and provids wrong output.

    Reply
  6. Neha nayak

    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.

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

    Reply
  8. gebreegzabher hailay

    this code makes me to be being concious, can u give me some what clarified?

    Reply

Leave a Reply