> For the complete documentation index, see [llms.txt](https://sharafat.gitbook.io/dsa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sharafat.gitbook.io/dsa/structures/graph/warshalls-algorithm.md).

# Warshall's Algorithm

## Warshall's Algorithm

To visualize this algorithm use this following site, you can check each steps of warshell algorithm from here,

{% embed url="<https://sharafat.is-a.dev/GraphCraft/>" %}

here's a test case, just use this input and click on **analyze data**.

```
0 0 0 1
1 0 1 1
1 0 0 1
0 0 1 0
```

> Open source project, source code is available on GitHub.

***

Warshall's Algorithm is used to find the transitive closure of a graph. The transitive closure of a graph is a matrix that shows whether there is a path from vertex i to vertex j. The algorithm is based on the idea that if there is a path from vertex i to vertex j, and there is a path from vertex j to vertex k, then there is a path from vertex i to vertex k.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int mat[n][n];

  // taking input
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> mat[i][j];

      // comment these two following two lines for path matrix
      // (because we need 0 for logical operations -> binary AND, OR)
      if (mat[i][j] == 0)     // if the value is 0,
        mat[i][j] = (int)1e7; // we set it to a higher value
    }
  }

  // warshall's algorithm
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]); // for shortest path
        // mat[i][j] = mat[i][j] || (mat[i][k] && mat[k][j]); // for path matrix
      }
    }
  }

  // printing matrix
  cout << endl;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << mat[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}
```

Here's a simple test case for this code,

```
4
0 0 0 1
1 0 1 1
1 0 0 1
0 0 1 0
```

{% hint style="info" %}
Above code can also work to find the path matrix. Follow the comments of the code.
{% endhint %}

***


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sharafat.gitbook.io/dsa/structures/graph/warshalls-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.