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 Image

Author Name :
Ranjith

Total : 5 Comments

Simillar Posts

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

  1. CapnCrax
    November 30th, 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
    June 16th, 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
    September 7th, 2011 at 6:45 pm

    Your program so simple i wish all the best

  4. Nassary
    September 7th, 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
    October 13th, 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);
    }

Leave a Reply

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

Free email signup