Warshall-Floyd algorithm
(old/warshall-floyd.inc.cpp)

• View this file on GitHub
• Last update: 2020-01-08 18:35:19+09:00

Code

/**
 * @brief Warshall-Floyd algorithm
 * @note O(n^3)
 * @param g is a digraph
 */
vector<vector<ll> > warshall_floyd(vector<vector<pair<int, ll> > > const & g) {
    int n = g.size();
    vector<vector<ll> > dist(n, vector<ll>(n, LLONG_MAX));
    REP (i, n) {
        dist[i][i] = 0;
        for (auto edge : g[i]) {
            int j; ll cost; tie(j, cost) = edge;
            dist[i][j] = cost;
        }
    }
    REP (k, n) {
        REP (i, n) if (dist[i][k] != LLONG_MAX) {
            REP (j, n) if (dist[k][j] != LLONG_MAX) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    return dist;
}

/**
 * @brief Warshall-Floyd algorithm for connectivity
 */
vector<vector<bool> > warshall_floyd(vector<vector<int> > const & g) {
    int n = g.size();
    vector<vector<bool> > conn(n, vector<bool>(n));
    REP (i, n) {
        conn[i][i] = true;
        for (int j : g[i]) {
            conn[i][j] = true;
        }
    }
    REP (k, n) REP (i, n) REP (j, n) {
        if (conn[i][k] and conn[k][j]) {
            conn[i][j] = true;
        }
    }
    return conn;
}

#line 1 "old/warshall-floyd.inc.cpp"
/**
 * @brief Warshall-Floyd algorithm
 * @note O(n^3)
 * @param g is a digraph
 */
vector<vector<ll> > warshall_floyd(vector<vector<pair<int, ll> > > const & g) {
    int n = g.size();
    vector<vector<ll> > dist(n, vector<ll>(n, LLONG_MAX));
    REP (i, n) {
        dist[i][i] = 0;
        for (auto edge : g[i]) {
            int j; ll cost; tie(j, cost) = edge;
            dist[i][j] = cost;
        }
    }
    REP (k, n) {
        REP (i, n) if (dist[i][k] != LLONG_MAX) {
            REP (j, n) if (dist[k][j] != LLONG_MAX) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    return dist;
}

/**
 * @brief Warshall-Floyd algorithm for connectivity
 */
vector<vector<bool> > warshall_floyd(vector<vector<int> > const & g) {
    int n = g.size();
    vector<vector<bool> > conn(n, vector<bool>(n));
    REP (i, n) {
        conn[i][i] = true;
        for (int j : g[i]) {
            conn[i][j] = true;
        }
    }
    REP (k, n) REP (i, n) REP (j, n) {
        if (conn[i][k] and conn[k][j]) {
            conn[i][j] = true;
        }
    }
    return conn;
}

Back to top page