Created
November 25, 2017 04:16
-
-
Save Suman2593/d357d24310b053838077dab5ca2b0c1d to your computer and use it in GitHub Desktop.
C Program on Dijkstra Algorithm for Finding Minimum Distance of Vertices from a Given Source in a Graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<stdio.h> | |
#include<conio.h> | |
#define INFINITY 9999 | |
#define MAX 10 | |
void dijkstra(int G[MAX][MAX],int n,int startnode); | |
int main() | |
{ | |
int G[MAX][MAX],i,j,n,u; | |
printf("Enter no. of vertices:"); | |
scanf("%d",&n); | |
printf("\nEnter the adjacency matrix:\n"); | |
for(i=0;i<n;i++) | |
for(j=0;j<n;j++) | |
scanf("%d",&G[i][j]); | |
printf("\nEnter the starting node:"); | |
scanf("%d",&u); | |
dijkstra(G,n,u); | |
return 0; | |
} | |
void dijkstra(int G[MAX][MAX],int n,int startnode) | |
{ | |
int cost[MAX][MAX],distance[MAX],pred[MAX]; | |
int visited[MAX],count,mindistance,nextnode,i,j; | |
//pred[] stores the predecessor of each node | |
//count gives the number of nodes seen so far | |
//create the cost matrix | |
for(i=0;i<n;i++) | |
for(j=0;j<n;j++) | |
if(G[i][j]==0) | |
cost[i][j]=INFINITY; | |
else | |
cost[i][j]=G[i][j]; | |
//initialize pred[],distance[] and visited[] | |
for(i=0;i<n;i++) | |
{ | |
distance[i]=cost[startnode][i]; | |
pred[i]=startnode; | |
visited[i]=0; | |
} | |
distance[startnode]=0; | |
visited[startnode]=1; | |
count=1; | |
while(count<n-1) | |
{ | |
mindistance=INFINITY; | |
//nextnode gives the node at minimum distance | |
for(i=0;i<n;i++) | |
if(distance[i]<mindistance&&!visited[i]) | |
{ | |
mindistance=distance[i]; | |
nextnode=i; | |
} | |
//check if a better path exists through nextnode | |
visited[nextnode]=1; | |
for(i=0;i<n;i++) | |
if(!visited[i]) | |
if(mindistance+cost[nextnode][i]<distance[i]) | |
{ | |
distance[i]=mindistance+cost[nextnode][i]; | |
pred[i]=nextnode; | |
} | |
count++; | |
} | |
//print the path and distance of each node | |
for(i=0;i<n;i++) | |
if(i!=startnode) | |
{ | |
printf("\nDistance of node%d=%d",i,distance[i]); | |
printf("\nPath=%d",i); | |
j=i; | |
do | |
{ | |
j=pred[j]; | |
printf("<-%d",j); | |
}while(j!=startnode); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment