## Path Matrix Using Floyd Warshall Algorithm

What is Path Matrix?
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

$path[i,j]&space;=&space;\begin{cases}&space;&&space;1,&space;\text{&space;}&space;\exists&space;\text{&space;a&space;path&space;from&space;i&space;to&space;j}&space;\\&space;&&space;\text{0&space;otherwise&space;}&space;\end{cases}$

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 as  $path_{k}$, So our definition becomes something like this :

$path_{k}[i,j]&space;=&space;\begin{cases}&space;&&space;1,&space;\text{&space;}&space;\exists&space;\text{&space;a&space;path&space;from&space;i&space;to&space;j&space;for&space;length&space;k}&space;\\&space;&&space;\text{0&space;otherwise&space;}&space;\end{cases}$

Solve to create $path_{k}$, we take help from the already created path matrix $path_{k-1}$, 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 $path_{0}$, we can easily prove that it is equal to our adjacency matrix of a graph, So, we found the base case, i.e. if $k&space;=&space;0$, we are dealing with nothing but the adjacency matrix, so, we compute path matrix for
$\text{k&space;=&space;1,&space;from&space;k&space;=&space;0&space;and&space;k&space;=&space;2&space;from&space;k&space;=&space;1&space;and&space;so&space;on...}$

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

$path_{k}[i,j]&space;=&space;(path_{k-1}[i,j]&space;\text{&space;}\vee\text{&space;}(path_{k-1}[i,k]&space;\text{&space;}&space;\wedge&space;\text{&space;}&space;path_{k-1}[k,j]))$

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

### Create Path matrix, and initialize it to adjacency matrixRepeat k = 1,2,3...n (number of vertices)Repeat for i = 1,2,3...nRepeat for j = 1,2,3...nif path[i,j] == 1 continueelse if path[i,k] == 1 and path[k,j] == 1set path[i,j] = 1exitThis Algorithm finds the path matrix in $n^3$, 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

// Storing our Path0
for (int i = 0; i < adjacency.size(); i++) {
for (int j = 0; j < adjacency.size(); 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
{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}
};

// 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;
}