Implement Dijkstra‘s algorithm to compute the Shortest path thru a given graph.

Implement Dijkstra‘s algorithm to compute the Shortest path thru a given graph.

Program Algorithm/Flowchart:

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[idex][i]==ed) then

Step 47: break

Step 48: end if

End

Program Code: 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 ");

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

{

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

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

break;

}

}

Program Output:

Enter the cost matrix

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

Enter the paths

2

Enter possible paths

1 2 3 4 5

1 2 3 4 5

Minimum cost 14