C program for Shortest path using Dijkstra's Algorithm

Saturday, 1 March 2014


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

void dijikstra(int G[MAX][MAX],int n, int startnode);
void main()
{ int G[MAX][MAX],i,j,n,u;
  clrscr();
  printf("\nEnter no. of vertices : ");
  scanf("%d",&n);
  printf("\nEnter adjacency matrix : ");
  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);
  dijikstra(G,n,u);
  getch();
}

void dijikstra(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
  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 is 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 exist 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("\n Distance of %d = %d ",i,distance[i]);
printf("\nPath = %d ",i);
j=i;
do {
    j=pred[j];
    printf("<- %d ",j);
  }while(j!=startnode);
     }
}


OUTPUT:-



Enter no. of vertices : 4

Enter adjacency matrix :
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

Enter the starting node : 1

 Distance of 0 = 1
Path = 0 <- 1
 Distance of 2 = 1
Path = 2 <- 1
 Distance of 3 = 2
Path = 3 <- 0 <- 1




1 comment

  1. Hello, I'm doing the same algorithm but in the other side, I mean I would have at the end of this algorithm the longest way between all nodes. I've modified conditions and it works for all nodes except between the first and the last node. Can you help ? Please !

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...
Related Posts Plugin for WordPress, Blogger...
 

Most Reading

Labels