 In Progress
Lesson 34, Topic 1
In Progress

# Warshall’s Algorithm

Lesson Progress
0% Complete

• Computes the transitive closure of a relation
• (Alternatively: all paths in a directed graph)
• Example of transitive closure:

• Main idea: a path exists between two vertices i, j, if
• there is an edge from i to j; or
• there is a path from i to j going through vertex 1; or
• there is a path from i to j going through vertex 1 and/or 2; or
• there is a path from i to j going through vertex 1, 2, and/or 3; or
• …
• there is a path from i to j going through any of the other vertices

• On the kth iteration,g p the algorithm determine if a path exists
between two vertices i, j using just vertices among 1,…,k allowed
as intermediate

Warshall’s Algorithm (matrix generation)

Recurrence relating elements R(k) to elements of R(k-1) is:

R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j])

It implies the following rules for generating R(k) from R(k-1):
Rule 1 If an element in row i and column j is 1 in R(k-1), it remains 1 in R(k)
Rule 2 If an element in row i and column j is 0 in R(k-1), it has to be changed to 1 in R(k) it has to be changed to 1 in R if and only if (k) if and only if the element in its row i and column k and the element in its column j and row k are both 1’s in R(k-1)

## Warshall’s Algorithm (pseudocode and analysis)

Time efficiency: (n3)
Space efficiency: Matrices can be written over their predecessors

## Input and Output

``````Input: The cost matrix of the graph.
0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

Output:
Matrix of all pair shortest path.
0 3 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0``````

## Implementation of Warshall’s Algorithm

``````#include<iostream>
#include<iomanip>
#define NODE 7
#define INF 999
using namespace std;

//Cost matrix of the graph
int costMat[NODE][NODE] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};

void floydWarshal() {
int cost[NODE][NODE];    //defind to store shortest distance from any node to any node
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
cost[i][j] = costMat[i][j];     //copy costMatrix to new matrix

for(int k = 0; k<NODE; k++) {
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
if(cost[i][k]+cost[k][j] < cost[i][j])
cost[i][j] = cost[i][k]+cost[k][j];
}

cout << "The matrix:" << endl;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++)
cout << setw(3) << cost[i][j];
cout << endl;
}
}

int main() {
floydWarshal();
}``````

Output :

``````The matrix:
0  3  5  4  6  7  7
3  0  2  1  3  4  4
5  2  0  1  3  2  3
4  1  1  0  2  3  3
6  3  3  2  0  2  1
7  4  2  3  2  0  1
7  4  3  3  1  1  0``````