Your Ad Here

Thursday, October 2, 2008

DIJKSRTRA'S ALGORITHM

/*Implementation of Shortest Path Algorithm(DIJKSRTRA's ALGORITHM) in C*/

#include< stdio.h>
#include< conio.h>
#include< process.h>
#include< string.h>
#include< math.h>
#define IN 99
#define N 6

int dijkstra(int cost[][N], int source, int target);

void main()
{
int cost[N][N],i,j,w,ch,co;
int source, target,x,y;
clrscr();
printf("\tShortest Path Algorithm(DIJKSRTRA's ALGORITHM\n\n");
for(i=1;i< N;i++)
for(j=1;j< N;j++)
cost[i][j] = IN;
for(x=1;x< N;x++)
{
for(y=x+1;y< N;y++)
{
printf("Enter the weight of the path between node %d and %d: ",x,y);
scanf("%d",&w);
cost [x][y] = cost[y][x] = w;
}
printf("\n");
}
printf("\nEnter The Source:");
scanf("%d", &source);
printf("\nEnter The target");
scanf("%d", &target);
co = dijsktra(cost,source,target);
printf("\nShortest Path: %d",co);
getch();
}

int dijsktra(int cost[][N],int source,int target)
{
int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
char path[N];
for(i=1;i< N;i++)
{
dist[i] = IN;
prev[i] = -1;
}
start = source;
selected[start]=1;
dist[start] = 0;
while(selected[target] ==0)
{
min = IN;
m = 0;
for(i=1;i< N;i++)
{
d = dist[start] +cost[start][i];
if(d< dist[i]&&selected[i]==0)
{
dist[i] = d;
prev[i] = start;
}
if(min>dist[i] && selected[i]==0)
{
min = dist[i];
m = i;
}
}
start = m;
selected[start] = 1;
}
start = target;
j = 0;
while(start != -1)
{
path[j++] = start+65;
start = prev[start];
}
path[j]='\0';
strrev(path);
printf("%s", path);
return dist[target];
}
/***** Output *********

Shortest Path Algorithm(DIJKSRTRA's ALGORITHM

Enter the weight of the path between node 1 and 2: 2
Enter the weight of the path between node 1 and 3: 3
Enter the weight of the path between node 1 and 4: 4
Enter the weight of the path between node 1 and 5: 5

Enter the weight of the path between node 2 and 3: 5
Enter the weight of the path between node 2 and 4: 2
Enter the weight of the path between node 2 and 5: 3

Enter the weight of the path between node 3 and 4: 1
Enter the weight of the path between node 3 and 5: 4

Enter the weight of the path between node 4 and 5: 5



Enter The Source:2

Enter The target4
CE
Shortest Path: 2
*/

10 comments:

gnana said...

You are very genius. i like this program

gnana said...

You are very genius. i like this program

fadli said...

this you'r program have syntax eror.
you look "dijsktra" not valid with "dijkstra"

thank you.

ritu said...

thanks for the program

Knight said...

THe program is very amazing, but i see the is an error ==>"Call to undefined function 'dijkstra' in function main()

Thank YOu

Anonymous said...

hey ur program doesnt handle a case...
when there is no path between source and destination

stack in c++ programme said...

stack

stack in c++ programme said...

stack

Anonymous said...

hey it is returning number of paths from source to destination instead of shortest path could please rectify it , i have the same doubt .thank you

pinky said...

hey instead of returning shortest path your program is returing number of paths from source to destination, could you please rectify it , i'm trying to solve this since long back couldn't get it please help me

Your Ad Here