← all categories

Floyd Warshall bd8743ee

Floyd-Warshall all-pairs shortest paths on a dense distance matrix (dist[i][j] = INF if no edge, dist[i][i] = 0). Mutates dist in place. Negative-cycle

Time: O(V^3). tested

content/graphs/floyd-warshall.h

template <typename W>
void floydWarshall(vector<vector<W>> &dist, W INF) {
    int n = (int)dist.size();
    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)  // guards INF+INF overflow
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}