DIJ.C

#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

void main()
{
    int G[MAX][MAX],i,j,n,u,e,fs=1,fw=1;
    char ch;
    clrscr();
   do{
    if(fw){
    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]);
    }
    if(fs){
    printf("\nEnter the starting node:");
    scanf("%d",&u);
    dijkstra(G,n,u);}
    printf("\n\nWhat do u want to do?\nChange Start node(s)\nChange Weight(w)\nQuit(q)\nEnter Choice: ");
    ch=getch();
    printf("%c",ch);
    if(ch=='s'||ch=='S')
	{fs=1;fw=0;
	 printf("\n");}
    if(ch=='w'||ch=='W')
	{fs=1;fw=1;
	 printf("\n\n");}
    if(ch=='q'||ch=='Q')
	break;
   }while(ch!='0');
    getch();
}

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);
    }
    return;
}