Implement Dijkstra’s algorithm to compute the shortest path through a network

NAME OF EXPERIMENT: Shortest Path

AIM: Implement Dijkstra’s algorithm to compute the shortest path through a network 

HARDWARE REQUIREMENTS: Intel based Desktop PC:-RAM of 512MB

SOFTWARE REQUIREMENT: Turbo C / Borland C

THEORY:

It is shortest path algorithm in which path length between each node is measured as function of distance, bandwidth, average traffic, communication cost, measured delay etc.In this Dijkstra’s algorithm, working node is changing continuously. We are calculating the link cost from working node to next node/hop.

PROGRAM ALGORITHM

Begin

Step1: Declare array path [5] [5], min, a [5][5], index, t[5];

Step2: Declare and initialize st=1,ed=5

Step 3: Declare variables i, j, stp, p, edp

Step 4: print “enter the cost “

Step 5: i=1

Step 6: Repeat step (7 to 11) until (i<=5)

Step 7: j=1

Step 8: repeat step (9 to 10) until (j<=5)

Step 9: Read a[i] [j]

Step 10: increment j

Step 11: increment i

Step 12: print “Enter the path”

Step 13: read p

Step 14: print “Enter possible paths”

Step 15: i=1

Step 16: repeat step(17 to 21) until (i<=p)

Step 17: j=1

Step 18: repeat step(19 to 20) until (i<=5)

Step 19: read path[i][j]

Step 20: increment j

Step 21: increment i

Step 22: j=1

Step 23: repeat step(24 to 34) until(i<=p)

Step 24: t[i]=0

Step 25: stp=st

Step 26: j=1

Step 27: repeat step(26 to 34) until(j<=5)

Step 28: edp=path[i][j+1]

Step 29: t[i]= [ti]+a[stp][edp]

Step 30: if (edp==ed) then

Step 31: break;

Step 32: else

Step 33: stp=edp

Step 34: end if

Step 35: min=t[st]

Step 36: index=st

Step 37: repeat step(38 to 41) until (i<=p)

Step 38: min>t[i]

Step 39: min=t[i]

Step 40: index=i

Step 41: end if

Step 42: print” minimum cost” min

Step 43: print” minimum cost pth”

Step 44: repeat step(45 to 48) until (i<=5)

Step 45: print path[index][i]

Step 46: if(path[index][i]==ed) then

Step 47: break

Step 48: end if

End

SOURCE CODE:

//Dijkstra's algorithm for finding shortest path for a given graph

#include<stdio.h>

void main ()

{

int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;

printf ("Enter the cost matrix\n");

for(i=1;i<=5;i++)

for(j=1;j<=5;j++)

scanf("%d",&a[i][j]);

printf("Enter the paths\n");

scanf("%d",&p);

printf("Enter possible paths\n");

for(i=1;i<=p;i++)

for(j=1;j<=5;j++)

scanf("%d",&path[i][j]);

for(i=1;i<=p;i++)

{

t[i]=0;

stp=st;

for(j=1;j<=5;j++)

{

edp=path[i][j+1];

t[i]=t[i]+a[stp][edp];

if(edp==ed)

break;

else

stp=edp;

}

}

min=t[st];index=st;

for(i=1;i<=p;i++)

{

if(min>t[i])

{

min=t[i];

index=i;

}

}

printf("Minimum cost:%d",min);

printf("\n Minimum cost path\n");

for(i=1;i<=5;i++)

{

printf("--> %d",path[index][i]);

if(path[index][i]==ed)

break;

}

}

OUTPUT: