Program 13 : Warshall's Algorithm

Develop a program to Implement Warshall’s Algorithm for a graph of n nodes.

Warshall’s Algorithm

Warshall's Algorithm, is used to find the transitive closure of a directed graph represented by an adjacency matrix.

#include <stdio.h>

#define MAX 100

void warshall(int graph[MAX][MAX], int n) {
    int i, j, k;

    // Apply Warshall's algorithm
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
            }
        }
    }
}

void displayMatrix(int graph[MAX][MAX], int n) {
    printf("Transitive Closure of the given graph:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX][MAX];
    int n;

    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    printf("Enter the adjacency matrix (use 1 for edge, 0 for no edge):\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    warshall(graph, n);
    displayMatrix(graph, n);

    return 0;
}

---

Warshall’s Algorithm

Warshall's Algorithm computes the transitive closure of a directed graph. That is, it determines whether a path exists between every pair of nodes (i, j).

Key Concept:

If there's a path from i to k and from k to j, then there's a path from i to j.

Algorithm Steps:

Given an adjacency matrix graph[n][n]:

1. Loop over all intermediate vertices k from 0 to n-1

2. For each pair (i, j), update:

   graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);

3. At the end, graph[i][j] == 1 means a path exists from i to j.

---

Input adjacency matrix for 4 nodes:

0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

Output transitive closure:

0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0