C++ Algorithm to find Path matrix of a graph.














































C++ Algorithm to find Path matrix of a graph.



(Pre-requisite - Basics of graph theory)

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 


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  , 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 

Algorithm to Create Path Matrix :

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

Comments