> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/graph/shortest-path/floyd-warshall.md).

# Floyd Warshall

## Problem Statement

\
All pair shortest Paths

## Intuition

```
Tc = V^3
```

### Links

<https://practice.geeksforgeeks.org/problems/implementing-floyd-warshall2042/1>

### Video Links

<https://www.youtube.com/watch?v=YbY8cVwWAvw&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
//User function template for C++

class Solution {
  public:
	void shortest_distance(vector<vector<int>>&matrix){
        int n = matrix.size();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) 
                if(matrix[i][j] == -1)
                    matrix[i][j] = 1e9;
                    
                
        }         
                
        
        for(int via = 0; via < n; via++){
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    matrix[i][j] = min( matrix[i][j] , matrix[i][via]+matrix[via][j]);
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 1e9)
                    matrix[i][j] = -1;
            }
        }  

        
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###