SHORTEST PATH ROUTING ALGORITHM IN C

SHORTEST PATH ROUTING 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:

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