# Warshall-Floyd Algorithm

```#include<bits/stdc++.h>
#define ll long long

// compute shortest paths between any pair of vertices
// negative weight - tolerant
struct WarshallFloyd {
// NOTE:
// vertices can be both ZERO-indexed or ONE-indexed
// DIRECTIONAL graph
int n;
ll **dist;
ll INF;

void init(int n_) {
n = n_;
dist = new ll *[n+1];
INF = 1; INF = INF * oo * oo;

for (int i = 0; i <= n; ++i) {
dist[i] = new ll[n+1];
}

for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j) {

if (i == j)
dist[i][j] = 0;
else
dist[i][j] = INF;
}

}

void addEdge(int u, int v, int w) {
if (dist[u][v] > w)
dist[u][v] = w;
}

void computeShortestPaths() {

// compute shortest paths
for (int k = 0; k <= n; ++k)
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];

// detect negative cycle
for(int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
if (dist[k][k] < 0 && dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = -INF;
}

ll getDistance(int u, int v) {
return dist[u][v];
}

};
```