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