#include<stdio.h>
main()
{
int node[50],pred[50],dist[50],status[50],path[50];
int n,source,dest,adj[50][50],i,j,k,x,temp;
int infinity=10000;
system("clear");
printf("Enter the number of nodes :");
scanf("%d",&n);
printf("Enter source node : ");
scanf("%d",&source );
printf("Enter the destination node : ");
scanf("%d",&dest);
if(source==dest)
{
printf("Source and destination are same");
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("Destination of %dth node to %d th node: ",i,j);
scanf("%d",&adj[i][j]);
}
pred[i]=0;
status[i]=0;
dist[i]=infinity;
node[i]=i;
}
dist[source]=0;
temp=source;
status[source]=1;
for(x=1;x<=n,x++)
{
for(j=1;j<=n;j++)
if((adj[source][j]!=0) && (status[j]==0))
{
pred[j]=node[source];
dist[j]=dist[source]+adj[source][j];
}
infinity=10000;
for(k=1;k<=n;k++)
if(status[k]==0)
if(dist[k]<infinity)
{
infinity=disk[k];
source=node[k];
}
if(source==dest)
break;
else
{
status[source]=1;
}
}
path[1]=dest;
k=2;
for(i=1;i<n;i++)
{
path[k]=pred[dest];
dest=pred[dest];
k++;
if(dest==temp)
break;
}
printf("Shortest path is");
for(k=i+1;k>=1;k++)
printf("-->%d",path[k]);
printf("\n");
}
/*---------------------------------------------------------------------------------------------------------------------
OUTPUT
--------
Enter the number of nodes : 3
Enter the source node : 1
Enter the destination node : 2
Destination of 1th node to 1th node:4
Destination of 1th node to 2th node:20
Destination of 1th node to 3th node:3
Destination of 2th node to 1th node:2
Destination of 2th node to 2th node:4
Destination of 2th node to 3th node:4
Destination of 3th node to 1th node:1
Destination of 3th node to 2th node:2
Destination of 3th node to 3th node:2
Shortest Path is: -->1-->3-->2
#include
ReplyDelete#include
#include
using namespace std;
#define INF 999
int dis[10];
int state[10];
int parent[10];
int path[15];
int p_no=-1;
int ecount=-1;
int V;
int graph[20][3];
void init_ss()
{
int i;
for(i=0;i<10;i++)
{
dis[i]=INF;
parent[i]=-1;
}
}
int weight(int u,int v)
{
int i;
for(i=0;i<=ecount;i++)
{
if((graph[i][0]==u&&graph[i][1]==v)||(graph[i][1]==u&&graph[i][0]==v))
return graph[i][2];
}
return INF;
}
int minimum()
{
int i,min=INF,index=-1;
for(i=0;idis[u]+weight(u,v))
{
dis[v]=dis[u]+weight(u,v);
parent[v]=u;
}
}
void dijkstra(int s)
{
int u,v;
dis[s]=0;
u=minimum();
while(u>=0)
{
path[++p_no]=u;
for(v=0;v>c;
if(c>0)
{
graph[++ecount][0]=i;
graph[ecount][1]=j;
graph[ecount][2]=c;
}
}
}
}
int main()
{
int s,i,u,v;
cout<<"\n\n\tEnter no: of vertices : ";
cin>>V;
read_graph(V);
init_ss();
cout<<"\n\n\tEnter the source vertex : ";
cin>>s;
dijkstra(s);
for(i=0;i<=p_no;i++)
{
u=path[i];
v=parent[path[i]];
if(v==-1)
cout<<"\n\n\tSource-->v"<v"<<u;
}
getch();
}