← all categories

Floyd Warshall Incremental 021d326d

Add a single edge (u, v, w) to an all-pairs-shortest-path matrix already computed by floyd-warshall.h, in O(n^2) instead of recomputing full O(n^3) Floyd-Warshall. Treats the new edge as one extra intermediate relaxation, same trick as the k-loop in Floyd-Warshall itself. Call once per edge added, in any order.

Time: O(n^2) per edge added. tested

content/graphs/floyd-warshall-incremental.h

template <typename W>
void addEdgeFW(vector<vector<W>> &dist, int u, int v, W w) {
    int n = (int)dist.size();
    dist[u][v] = min(dist[u][v], w);
    dist[v][u] = dist[u][v];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = min({dist[i][j], dist[i][u] + dist[u][v] + dist[v][j], dist[i][v] + dist[v][u] + dist[u][j]});
}