Home > Source Codes > Software Programs > C++ Programs > Data structure > C++ program to solve the single source shortest path problem Using Dijkstra’s algorithm

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

Thursday, March 11th, 2010

/* 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

Avatar of Ranjith

Author Name :
Ranjith

Total : 10 Comments

Simillar Posts

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

  1. CapnCrax says:
    November 30, 2010 at 5:34 am

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

  2. usman says:
    June 16, 2011 at 10:45 am

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

  3. Nassary says:
    September 7, 2011 at 6:45 pm

    Your program so simple i wish all the best

  4. Nassary says:
    September 7, 2011 at 7:50 pm

    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

  5. lovejit says:
    October 13, 2011 at 11:09 am

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

  6. Ankit jain says:
    April 30, 2012 at 11:51 am

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

  7. Neha nayak says:
    May 2, 2012 at 10:15 am

    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.

  8. anand says:
    August 13, 2012 at 10:16 am

    wrong program !!!

  9. ankita says:
    August 22, 2012 at 2:38 pm

    boringgggggggggggggggggggggg!!!!!!!!!!!!!!!!!!!!!!!

  10. sameer patil says:
    August 23, 2012 at 4:24 pm

    zop

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup

Email: