DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Dijikshtra's Shortest Path In C

04.14.2010
| 1501 views |
  • submit to reddit
        // the code takes no. of nodes and adjency matrix as input and prints path and distance 
// for specified source and destination

#include<stdio.h>
#include<conio.h>
#define infinity 1000



class queue
{
  public:
  int top;
  int rear;
  int a[10];
  queue()
  {
  top=rear=-1;
  }

  void push(int n)
  {
   a[++top]=n;
  }

  int isempty()
  {
  if(top==rear)
  return 1;
  return 0;
  }
  int del()
  {
  int temp=a[++rear];
  if(rear==top)
  {
       rear=top=-1;
  }
  return temp;
  }
};


void main()
{
  clrscr();
  int n,mat[10][10],s,d,path[10],dist[10],v,w;
  queue q;
  printf("Enter no. of nodes::");
  scanf("%d",&n);
  printf("Enter the adjancey matrix(enter 0 for diagonal elements)::\n");
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      scanf("%d",&mat[i][j]);

  printf("Enter the source node::");
  scanf("%d",&s);
  printf("Enter the destination node::");
  scanf("%d",&d);
  q.push(s);
  dist[s]=0;
  for(i=1;i<=n;i++)
   {
   if(i!=s)
   {
   q.push(i);
   dist[i]=infinity;
   }
   path[i]=0;
   }
  while(!q.isempty())
  {
    v=q.del();
      for(i=1;i<=n;i++)
      { if(mat[v][i]!=0)
	{
	w=i;
	if(dist[v]+mat[v][w]<dist[w])
	{
	dist[w]=dist[v]+mat[v][w];
	path[w]=v;
	}
	}
      }
  }
 getch();
 printf("%d",d);
 do
 {
 printf("<-%d",path[d]);
 d=path[d];
 }
 while(d!=s);
 getch();
}