Untitled
unknown
plain_text
a year ago
3.3 kB
3
Indexable
/* Program of shortest path between two node in graph using Djikstra algorithm */ #include<stdio.h> #define MAX 10 #define TEMP 0 #define PERM 1 #define infinity 9999 struct node { int predecessor; int dist; /minimum distance of node from source/ int status; }; int adj[MAX][MAX]; int n; void main() { int i,j; int source,dest; int path[MAX]; int shortdist,count; create_graph(); printf("The adjacency matrix is :\n"); display(); while(1) { printf("Enter source node(0 to quit) : "); scanf("%d",&source); printf("Enter destination node(0 to quit) : "); scanf("%d",&dest); if(source==0 || dest==0) exit(1); count = findpath(source,dest,path,&shortdist); if(shortdist!=0) { printf("Shortest distance is : %d\n", shortdist); printf("Shortest Path is : "); for(i=count;i>1;i--) printf("%d->",path[i]); printf("%d",path[i]); printf("\n"); } else printf("There is no path from source to destination node\n"); }/End of while/ }/End of main()/ create_graph() { int i,max_edges,origin,destin,wt; printf("Enter number of vertices : "); scanf("%d",&n); max_edges=n*(n-1); for(i=1;i<=max_edges;i++) { printf("Enter edge %d(0 0 to quit) : ",i); scanf("%d %d",&origin,&destin); if((origin==0) && (destin==0)) break; printf("Enter weight for this edge : "); scanf("%d",&wt); if( origin > n || destin > n || origin<=0 || destin<=0) { printf("Invalid edge!\n"); i--; } else adj[origin][destin]=wt; }/End of for/ }/End of create_graph()/ display() { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%3d",adj[i][j]); printf("\n"); } }/End of display()/ int findpath(int s,int d,int path[MAX],int *sdist) { struct node state[MAX]; int i,min,count=0,current,newdist,u,v; *sdist=0; /* Make all nodes temporary */ for(i=1;i<=n;i++) { state[i].predecessor=0; state[i].dist = infinity; state[i].status = TEMP; } /Source node should be permanent/ state[s].predecessor=0; state[s].dist = 0; state[s].status = PERM; /Starting from source node until destination is found/ current=s; while(current!=d) { for(i=1;i<=n;i++) { /*Checks for adjacent temporary nodes */ if ( adj[current][i] > 0 && state[i].status == TEMP ) { newdist=state[current].dist + adj[current][i]; /Checks for Relabeling/ if( newdist < state[i].dist ) { state[i].predecessor = current; state[i].dist = newdist; } } }/End of for/ /Search for temporary node with minimum distand make it current node/ min=infinity; current=0; for(i=1;i<=n;i++) { if(state[i].status == TEMP && state[i].dist < min) { min = state[i].dist; current=i; } }/End of for/ if(current==0) /If Source or Sink node is isolated/ return 0; state[current].status=PERM; }/End of while/ /* Getting full path in array from destination to source */ while( current!=0 ) { count++; path[count]=current; current=state[current].predecessor; } /Getting distance from source to destination/ for(i=count;i>1;i--) { u=path[i]; v=path[i-1]; *sdist+= adj[u][v]; } return (count); }/End of findpath()/
Editor is loading...
Leave a Comment