4.dijektra

File: /home/saiesh/ADS/Assignment No 4/ads4.cpp
#include<iostream>
#include<string>
#define IN 9999
#define N 6
using namespace std;
int n;
int dijktra(int cost[N][N], int source, int target);
int dijktra(int cost[N][N], int source, int target)
{
int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
for(i=1;i<=n;i++)
{
dist[i]=IN;
prev[i]=-1;
}
start=source;
selected[start]=1;
dist[start]=0;
while(selected[target]==0)
{
min=IN;
m=0;
for(i=1;i<=n;i++)
{
d=dist[start]+cost[start][i];
if(d<dist[i]&&selected[i]==0)
{
dist[i]=d;
prev[i]=start;
}
else
dist[i]=dist[i];
if(min>dist[i]&&selected[i]==0)
{
min=dist[i];
m=i;
}
}
start=m;
selected[start]=1;
}
cout<<"\nShortest path is: "<<target;
i=target;
while(prev[i]!=source)
{
cout<<" -> "<<prev[i];
i=prev[i];
}
cout<<" -> "<<source;
return dist[target];
}
int main()
{
int cost[N][N],i,j,w,ch,co;
char ans;
int source,target,x,y;
cout<<"\n\tShortest Path Algorithm\n";
cout<<"\nEnter the number of vertices: ";
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=IN;
for(i=1;i<=n;i++)
{
Page 1 of 2File: /home/saiesh/ADS/Assignment No 4/ads4.cpp
Page 2 of 2
for(j=i+1;j<=n;j++)
{
cout<<"Enter the weight of the path between the node
"<<i<<" and "<<j<<": ";
cin>>w;
cost[i][j]=cost[j][i]=w;
}
}
do
{
cout<<"\nEnter the source: ";
cin>>source;
cout<<"Enter the target: ";
cin>>target;
co=dijktra(cost,source,target);
cout<<"\nShortest distance is: "<<co;
cout<<"\nDo you want to continue? ";
cin>>ans;
} while(ans=='y');
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads4.cpp
saiesh@saiesh :~$ ./a.out
Shortest Path Algorithm
Enter
Enter
Enter
Enter
Enter
Enter
Enter
the
the
the
the
the
the
the
number
weight
weight
weight
weight
weight
weight
of
of
of
of
of
of
of
vertices: 4
the path between
the path between
the path between
the path between
the path between
the path between
Enter the source: 1
Enter the target: 3
Shortest path is: 3 -> 4 -> 2 -> 1
Shortest distance is: 14
Do you want to continue? y
Enter the source: 3
Enter the target: 1
Shortest path is: 1 -> 2 -> 4 -> 3
Shortest distance is: 14
Do you want to continue? n
saiesh@saiesh :~$ */
the
the
the
the
the
the
node
node
node
node
node
node
1
1
1
2
2
3
and
and
and
and
and
and
2:
3:
4:
3:
4:
4:
5
9999
13
11
4
5