Path matrix is a binary matrix (contains 0s or 1s), Let's call our path matrix just "path" for easy reference, we define path[i,j] as

Now, to create this **Path Matrix, **we have an un-efficient method, where we find path matrix for each path length and at-last we add all matrices to get final path matrix, **Warshall **devised an efficient approach, but we still need to find path matrix for each path length, i.e. when path length is 1, 2, 3, and so on.... So, we denote our path matrix which contains paths of length **k **as , So our definition becomes something like this :

Solve to create , we take help from the already created path matrix , which signifies that, we are using Dynamic Programming, to solve the problem from already computed solution.

So, according to the perspective of Dynamic programming, we need some base case,

If we take a look at , we can easily prove that it is equal to our adjacency matrix of a graph, So, we found the base case, i.e. if , we are dealing with nothing but the adjacency matrix, so, we compute path matrix for

But, what **decision we have to make when we are not in base case, **To answer this question I will take the help of a simple diagram**Observe that, if we are finding path from A to B, **__if there exist path then there is no issue, but if not, we search in each of the existing node for a node K, such that if there exist path from node A to K and K to B, then we can say that there exist path from node A to B,__ Mathematically

So, now with all necessary information, we can create our algorithm like this

- Create Path matrix, and initialize it to adjacency matrix
- Repeat k = 1,2,3...n (number of vertices)
- Repeat for i = 1,2,3...n
- Repeat for j = 1,2,3...n
- if path[i,j] == 1
- continue
- else if path[i,k] == 1 and path[k,j] == 1
- set path[i,j] = 1
- exit

This Algorithm finds the path matrix in , where n is the number of vertices.

Below is the c++ implementation for finding path matrix.

#include<bits/stdc++.h> using namespace std; // Algorithm to Find Path Matrix vector<vector<int>> FindPathMatrix(vector<vector<int>> adjacency) { vector<vector<int>> path_matrix(adjacency.size()); // Storing our Path0 for (int i = 0; i < adjacency.size(); i++) { for (int j = 0; j < adjacency.size(); j++) { path_matrix[i].push_back(adjacency[i][j]); } } // Main algorithm starts here for (int k = 1; k < adjacency.size(); k++) { for (int i = 1; i < adjacency.size(); i++) { for (int j = 1; j < adjacency.size(); j++) { path_matrix[i][j] = (path_matrix[i][j] == 1 or (path_matrix[i][k] == 1 and path_matrix[k][j] == 1) ); } } } return path_matrix; } int main() { /* We will find path matrix for this graph 5 ^ | 3 -> 4 ^ ^ | | 1 -> 2 */ // Example Adjacency matrix, row 0 and column 0 doesn't contribute to path matrix vector<vector<int>> adjacency_matrix{ {0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0} }; auto pathMatrix = FindPathMatrix(adjacency_matrix); // Output the path matrix for (int i = 1; i < pathMatrix.size(); i++) { for (int j = 1; j < pathMatrix.size(); j++) { cout << pathMatrix[i][j] << " "; } cout << endl; } return 0; }

Name | Views | Likes |
---|---|---|

C++ program to find Minimum of each subarrays in Linear Time. | 70 | 0 |

C++ Algorithm to find Path matrix of a graph. | 99 | 0 |

Implement BODMAS using C++. | 213 | 0 |

Shell Sort. | 240 | 0 |

3n+1 Problem Solution using C++. | 104 | 0 |

## Comments