Wednesday, May 15, 2013

Implementation of Dijkstra's algorithm(Finding shortest path) using C language



C Program to implement Dijkstra's algorithm. Dijkstra's Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra's Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim's algorithm. Read more about C Programming Language .

/***********************************************************
* You can use all the programs on  www.engineercse.blogspot.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact sm.rumi18@gmail.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                       Coding is Poetry !!!
***********************************************************/

#include "stdio.h"
#include "conio.h"
#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])
{
 int i,u,count,w,flag[10],min;
 for(i=1;i<=n;i++)
  flag[i]=0,dist[i]=cost[v][i];
 count=2;
 while(count<=n)
 {
  min=99;
  for(w=1;w<=n;w++)
   if(dist[w]
    min=dist[w],u=w;
  flag[u]=1;
  count++;
  for(w=1;w<=n;w++)
   if((dist[u]+cost[u][w]
    dist[w]=dist[u]+cost[u][w];
 }
}

void main()
{
 int n,v,i,j,cost[10][10],dist[10];
 clrscr();
 printf("\n Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n Enter the cost matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
   scanf("%d",&cost[i][j]);
   if(cost[i][j]==0)
    cost[i][j]=infinity;
  }
 printf("\n Enter the source matrix:");
 scanf("%d",&v);
 dij(n,v,cost,dist);
 printf("\n Shortest path:\n");
 for(i=1;i<=n;i++)
  if(i!=v)
   printf("%d->%d,cost=%d\n",v,i,dist[i]);
 getch();
}
Read more Similar C Programs


To get regular updates on new C programs, Algorithm problem solution,

No comments:

Post a Comment