Warshall Froyd
(library/graph/shortest_path/warshall_froyd.hpp)

• View this file on GitHub
• Last update: 2026-01-21 11:49:22+09:00
• Include: #include "library/graph/shortest_path/warshall_froyd.hpp"

Warshall Froyd

できること

• 全頂点対の最小コストを求める
• 複数始点
  • dis: dis[i][j] := 頂点までの最小コスト
  • negativeCycle: 負の閉路がある場合true

計算量

$O(N^3)$

使い方

auto [dis, negativeCycle] = warshall_froyd(G);

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)

Verified with

• グラフ - WarshallFroydのテスト (tests/graph.shortest_path.warshall_froyd.test.cpp)

Code

#pragma once
#include "library/graph/base/graph.hpp"
pair<vector<vector<long long>>, bool> warshall_froyd(const Graph &G) {
    int N = G.size();
    vector<vector<long long>> dis(N, vector<long long>(N, INF));
    for (int v = 0; v < N; ++v) {
        dis[v][v] = 0;
        for (auto &&[from, to, cost, idx] : G[v]) {
            dis[v][to] = min(dis[v][to], cost);
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            if (dis[i][k] == INF) continue;
            for (int j = 0; j < N; ++j) {
                if (dis[k][j] == INF) continue;
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    bool negativeCycle = false;
    for (int i = 0; i < N; ++i) {
        if (dis[i][i] < 0) {
            negativeCycle = true;
            break;
        }
    }
    return {dis, negativeCycle};
}

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 3 "library/graph/base/graph.hpp"
struct Graph {
    int N;
    vector<vector<Edge>> G;
    int es;
    Graph() = default;
    Graph(int N) : N(N), G(N), es(0) {}
    const vector<Edge> &operator[](int v) const { return G[v]; }
    int size() const { return N; }
    void add(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es++));
    }
    void add_both(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es));
        G[to].push_back(Edge(to, from, cost, es++));
    }
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u += padding, v += padding;
            long long cost = 1ll;
            if (weighted) cin >> cost;
            if (directed) {
                add(u, v, cost);
            } else {
                add_both(u, v, cost);
            }
        }
    }
};
#line 3 "library/graph/shortest_path/warshall_froyd.hpp"
pair<vector<vector<long long>>, bool> warshall_froyd(const Graph &G) {
    int N = G.size();
    vector<vector<long long>> dis(N, vector<long long>(N, INF));
    for (int v = 0; v < N; ++v) {
        dis[v][v] = 0;
        for (auto &&[from, to, cost, idx] : G[v]) {
            dis[v][to] = min(dis[v][to], cost);
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            if (dis[i][k] == INF) continue;
            for (int j = 0; j < N; ++j) {
                if (dis[k][j] == INF) continue;
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    bool negativeCycle = false;
    for (int i = 0; i < N; ++i) {
        if (dis[i][i] < 0) {
            negativeCycle = true;
            break;
        }
    }
    return {dis, negativeCycle};
}

Back to top page