CREATE OWN LIBRARY

Overview:

         All pair shortest path: Also known as Floyd-Warshall algorithm, it is a generalized shortest path problem where the objective is to find the shortest path between all pairs of vertices in a given graph.

         Dynamic Programming:Dynamic Programming is a method for solving a problem by breaking it down into subproblems which are overlapping and, optimally solving each of those subproblems exactly once while storing their solutions state (optimal substructure)

         Dynamic Programming approach to Floyd-Warshall: Given an n x n distance matrix Dof a GraphG , w_ij  is the distance between vertex i to vertex j written in i^th row and j^th column of D and n is the number of vertices. The dynamic programming formulation for Floyd Warshall,

d_ij⁽⁰⁾ = w_ij

d_ij^(k) = min(d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1)) for k ≥ 1

where d_ij is the shortest path between vertex i to vertex j.

Procedure:

Consider the following Graph and its distance matrix D,

Step 1: From the Dynamic programming formulation we have D⁰ = D. We consider k  as the intermediate vertices in each iteration i.e. k ={1, 2, 3, 4}.In the first iteration, for k = 1, we create a matrixD¹ where d_ij⁽¹⁾represents the 

 values in the i^th row and j^th column ofD¹ and d_ij⁽¹⁾= min(d_ij⁽⁰⁾, d_ik⁽⁰⁾ + d_kj⁽⁰⁾). We get the following matrix,

For example, d₂₄⁽¹⁾ = min(d₂₄⁽⁰⁾, d₂₁⁽⁰⁾ + d₁₄⁽⁰⁾). We have d₂₄⁽⁰⁾ = infinity, d₂₁⁽⁰⁾ = 8and  d₁₄⁽⁰⁾ = 7from D⁰. So, d₂₄⁽¹⁾ = min(infinity, 15) = 15.

Notice that, in all the iteration, the k^throw and k^th column remains the same as the previous iteration. And the diagonal values will always be 0 as there are no self-loops.

Step 2: For the next iteration, k = 2, and we continue with the same process to generate D²

Step 3:For the next iteration,k = 2, and we continue with the same process to generate D³

Step 4: For the next iteration, 

For the next iteration, k = 4, and we continue with the same process to generate D⁴which is the all pair shortest path matrix.

Algorithm:

Input:

1.    An weighted graph

Output:

1.     Displays all pair shortest paths available in the given graph

Algo:

Step 1: Start

Step 2: Set max     50

Step 3: Defining inputGraph function

               void inputGraph(int distance[][max], int shortestDistance[][max], int V)

                       Display "Enter the distance matrix of the graph: [99 for infinity]”

                       for i = 0 to i < V repeat

                                   for j = 0 to j < V repeat

                                               Check if(i == j)

                                                           Set distance[i][j]     0

                                              Otherwise

                                                           Display "Enter distance from vetex (i+1) to vertex                                                    (j+1)"

                                                           Read distance[i][j]

                                               shortestDistance[i][j]     distance[i][j]

                                               Set j     j + 1

                                   Set i     i + 1

Step 4: Defining printMatrix function

           void printMatrix(int distance[][max], int V)

                       for i = 0 to i < V repeat

                                   for j = 0 to j < V repeat

                                               Check if(distance[i][j] == 99)

                                                           Display “i”

                                               Otherwise

                                                           Display distance[i][j]

                                               Set j     j + 1

                                   Set i     i + 1

Step 5: Defining calculateShortestPath function

           void calculateShortestPath(int shortestDistance[][max], int V)

                       Set int interVertex     Null

                       for interVertex = 0 to interVertex < V repeat

                                   for i = 0 to i < V repeat

                                               for j = 0 to j < V repeat

                                                          Check if(shortestDistance[i][interVertex] +                                                                                shortestDistance[interVertex][j] <                                                                                  shortestDistance[i][j])

                                                                       Set shortestDistance[i][j]                                                                                                 shortestDistance[i][interVertex] +                                                                                             shortestDistance[interVertex][j]

                                                          Set j     j + 1

                                               Set i     i + 1

Step 6: Defining main function

           Set int distance[max][max]     Null

           Set int shortestDistance[max][max]     Null

           Display “Enter the number of vertices”

           Read V

           Call inputGraph(distance, shortestDistance, V)

           Display “Input Matrix: [i denotes infinity]”

           Call printMatrix(distance, V)

           Call calculateShortestPath(shortestDistance, V)

           Display "The shortest path matrix: [i denotes infinity]”

           Call printMatrix(shortestDistance, V)

Step 7: Stop