library/graph/shortest_path/WarshallFloyd.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/graph/shortest_path/WarshallFloyd.hpp"

Depends on

build/pch/stdc++.hpp

Verified with

test/AOJ/GRL_1_C.test.cpp

Code

template <typename WG, typename T = typename WG::weight_type>
std::vector<std::vector<T>> warshall_floyd(const WG &g) {
    int n = g.n;
    static constexpr T INF = std::numeric_limits<T>::max() / 2;
    std::vector d(n, std::vector<T>(n, INF));
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    for (const auto &e : g.edges)
        if (d[e.from][e.to] > e.weight)
            d[e.from][e.to] = e.weight;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (d[i][k] < INF)
                for (int j = 0; j < n; j++)
                    if (d[k][j] < INF)
                        if (d[i][j] > d[i][k] + d[k][j])
                            d[i][j] = d[i][k] + d[k][j];
    return d;
}

#line 1 "library/graph/shortest_path/WarshallFloyd.hpp"
template <typename WG, typename T = typename WG::weight_type>
std::vector<std::vector<T>> warshall_floyd(const WG &g) {
    int n = g.n;
    static constexpr T INF = std::numeric_limits<T>::max() / 2;
    std::vector d(n, std::vector<T>(n, INF));
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    for (const auto &e : g.edges)
        if (d[e.from][e.to] > e.weight)
            d[e.from][e.to] = e.weight;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (d[i][k] < INF)
                for (int j = 0; j < n; j++)
                    if (d[k][j] < INF)
                        if (d[i][j] > d[i][k] + d[k][j])
                            d[i][j] = d[i][k] + d[k][j];
    return d;
}