Page No.

 ASSIGNMENT NO: -

Write a program in c to find the shortest path of a connected graph using floyd’s algo

 THEORY: - The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The
problem is to find shortest distances between every pair of vertices in a given edge weighted
directed Graph.

Example:

Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }
which represents the following graph
10
(0)------->(3)
| /|\
5| |
| |1
\|/ |
(1)------->(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.
Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
 ALGORITHM: -

 Variable Listing: -

Variable Name Type Purpose

a[20][20] integer Indicates the initial weighted

graph in matrix form
n integer Indicates the no of vertices to
be input
i,j,k integer Used in operation where direct
path or alternative path from a
vertex to a another vertex is
checked

STEP 1: - Input the matrix a[20][20]

Date: -
 Page No.

STEP 2: - Input i,j,n

STEP 3: - Define a function prototype- int Floyd(int a[20][20], int n)

STEP 4: - Input “enter the no of vertices”

STEP 5: - Read n

STEP 6: - Display “give the initial weighted graph in matrix form(give 9999 in place of infinity)”

STEP 7: - Repeat through step 8 to step for i=0 to n do

STEP 8: - Repeat through step 9 to step for j=0 to n do

STEP 9: - Input “enter the value of a[%d][%d]”,i,j

STEP 10: - Read a[i][j]

[End of inner for loop]

[End of outer for loop]

STEP 11: - Display “the input weight matrix is:”

STEP 12: - Repeat through step 13 to step 18 for i=0 to n do

STEP 13: - Repeat through step 14 to step 17 for j=0 to n do

STEP 14: - If(a[i][j]=9999) then

STEP 15: - Display “inf\t”

STEP 16: - Else

STEP 17: - Display “%d\t”,a[i][j]

[End of inner for loop]

STEP 18: - Print “\n”

[End of outer for loop]

STEP 19: - Call the function- Floyd(a,n)

STEP 20: - Display “the final matrix where we can find the shortest distance”

STEP 21: - Repeat through step 22 to step for i=0 to n do

STEP 22: - Repeat through step 23 to step for j=0 to n do

STEP 23: - Display “%5d”,a[i][j]

[End of inner for loop]

STEP 24: - Print “\n”

[End of outer for loop]

Date: -
 Page No.

STEP 25: - Stop

Method for calling the function –int Floyd(int a[20][20],int n): -

STEP 1: - Input k,i,j

STEP 2: - Repeat through step 3 to step for k=0 to n do

STEP 3: - Repeat through step 4 to step for i=0 to n do

STEP 4: - Repeat through step 5 to step for j=0 to n do

STEP 5: - If(a[i][j]>(a[i][k]+a[k][j]) then

STEP 6: - Set a[i][j]=a[i][k]+a[k][j]

[End of inner for loop]

[End of inner for loop]

[End of outer for loop]

STEP 7: - End

 INPUT & OUTPUT: -

 Set 1: -

enter no of vertices 3

give the initial weighted graph in weight matrix form(give 9999 in the place of infinity)

enter the value of a[0][0] 3

enter the value of a[0][1] 1

enter the value of a[0][2] 8

enter the value of a[1][0] 4

enter the value of a[1][1] 9

enter the value of a[1][2] 6

enter the value of a[2][0] 2

enter the value of a[2][1] 5

enter the value of a[2][2] 8

the input weight matrix is

3 1 8

4 9 6

2 5 8

Date: -
 Page No.

the final matrix where we can find the shortest distance

--------------------------------

Process exited after 24.43 seconds with return value 0

Press any key to continue . . .

 Set 2: -

enter no of vertices 4

give the initial weighted graph in weight matrix form(give 9999 in the place of infinity)

enter the value of a[0][0] 3

enter the value of a[0][1] 6

enter the value of a[0][2] 1

enter the value of a[0][3] 2

enter the value of a[1][0] 9

enter the value of a[1][1] 5

enter the value of a[1][2] 7

enter the value of a[1][3] 8

enter the value of a[2][0]1

enter the value of a[2][1] 4

enter the value of a[2][2] 5

enter the value of a[2][3] 9

Date: -
 Page No.

enter the value of a[3][0] 5

enter the value of a[3][1] 1

enter the value of a[3][2] 9

enter the value of a[3][3] 4

the input weight matrix is

3 6 1 2

9 5 7 8

1 4 5 9

5 1 9 4

the final matrix where we can find the shortest distance

--------------------------------

Process exited after 46.61 seconds with return value 0

Date: -
 Page No.

Press any key to continue . . .

 DISCUSSION: -We initialize the solution matrix same as the input graph matrix as a first step.
Then we update the solution matrix by considering all vertices as an intermediate vertex. The
idea is to one by one pick all vertices and updates all shortest paths which include the picked
vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an
intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate
vertices. For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it
is.

2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as
dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]

3) The above program only prints the shortest distances. We can modify the solution to print the
shortest paths also by storing the predecessor information in a separate 2D matrix.
Also, the value of INF can be taken as INT_MAX from limits.h to make sure that we handle
maximum possible value. When we take INF as INT_MAX, we need to change the if condition in
the above program to avoid arithmetic overflow.

Date: -