C - Programming Guide

C - Program to Implement Dijkstra's Algorithm

#include<stdio.h>
#include<conio.h>
#define MAX 30
#define infinity 9999

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

void main()
{
  int g[MAX][MAX],i,j,n;
  int edges,u,v,w;
  clrscr();

  printf("\nEnter the no. of Vertices::");
  scanf("%d",&n);
  printf("\nEnter the no. of Edges::");
  scanf("%d",&edges);
  printf("\nEnter the Edges(u,v,weight)::\n");
  for(i=0;i<edges;i++)
  {
    scanf("%d%d%d",&u,&v,&w);
    g[u][v]=g[v][u]=w;
  }

  printf("\nEnter the Start node::");
  scanf("%d",&u);
  dijkstra(g,n,u);
  getch();
}

void dijkstra(int g[MAX][MAX],int n,int startnode)
{
  int cost[MAX][MAX],dist[MAX],pred[MAX];
  int visited[MAX],count,mindist,nextnode,i,j;

  for(i=0;i<n;i++)                                 //create cost matrix
    for(j=0;j<n;j++)
        if(g[i][j]==0)
            cost[i][j]=infinity;
        else
            cost[i][j]=g[i][j];

  for(i=0;i<n;i++)
  {
    dist[i]=cost[startnode][i];
    pred[i]=startnode;
    visited[i]=0;
   }

   visited[startnode]=1;
   dist[startnode]=0;
   count=1;
   while(count<n-1)
   {
     mindist=infinity;
     //next node is node at min. distance
     for(i=0;i<n;i++)
    if(dist[i]<mindist && !visited[i])
    {
      mindist=dist[i];
      nextnode=i;
    }
     visited[nextnode]=1;
     //check if better path exists
     for(i=0;i<n;i++)
    if(!visited[i])
        if(mindist+cost[nextnode][i]<dist[i])
        {
            dist[i]=mindist+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 %d=%d",i,dist[i]);
      printf("\nPath=%d",i);
      j=i;
      do
      {
       j=pred[j];
       printf("<-%d",j);
      }while(j!=startnode);
    }
}