Warshall–Floyd 法
(include/emthrm/graph/shortest_path/warshall-floyd.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/graph/shortest_path/warshall-floyd.hpp"

任意の2頂点間の最短路を求める全点対最短路問題を解けるアルゴリズムである。

時間計算量

$O({\lvert V \rvert}^3)$

仕様

template <typename T>
struct WarshallFloyd;

• T：辺のコストを表す型

メンバ変数

名前	説明
std::vector<std::vector<T>> graph	graph[s][t] は始点 $s$, 終点 $t$ を結ぶ辺の最小コストを表す。ただし辺が存在しないときは $\infty$ となる。
std::vector<std::vector<T>> dist	dist[s][t] は始点 $s$ から終点 $t$ までの最短距離を表す。ただし到達できないときは $\infty$ となる。

メンバ関数

名前	効果・戻り値	要件
WarshallFloyd(const std::vector<std::vector<T>>& graph, const T inf);	隣接行列 $\mathrm{graph}$ に対してオブジェクトを構築する。	隣接行列は $\infty$ で初期化している。
void add(const int src, const int dst, const T cost);	重み $\mathrm{cost}$ の辺 $(\mathrm{src}, \mathrm{dst})$ をグラフに加える。
void calc();	辺をグラフに追加した後、全点対最短路を構築する。
bool has_negative_cycle() const;	グラフが負の閉路をもつか。
std::vector<int> build_path(const int s, const int t) const;	始点 $s$ から終点 $t$ までの最短路。ただし到達できないときは空配列を返す。

参考文献

• Robert W. Floyd: Algorithm 97: Shortest path, Communications of the ACM, Vol. 5, No. 6, p. 345 (1962). https://doi.org/10.1145/367766.368168
• Stephen Warshall: A Theorem on Boolean Matrices, Journal of the ACM, Vol. 9, No. 1, pp. 11–12 (1962). https://doi.org/10.1145/321105.321107
• http://www.prefield.com/algorithm/graph/floyd_warshall.html
• https://ei1333.github.io/luzhiled/snippets/graph/warshall-floyd.html

TODO

• Johnson’s algorithm
  • http://www.prefield.com/algorithm/graph/johnson.html
  • https://inzkyk.github.io/algorithms/all_pairs_shortest_paths/johnsons_algorithm/

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0526/review/4082670/emthrm/C++14

Verified with

• グラフ/最短路問題/Warshall–Floyd 法 (test/graph/shortest_path/warshall-floyd.test.cpp)

Code

#ifndef EMTHRM_GRAPH_SHORTEST_PATH_WARSHALL_FLOYD_HPP_
#define EMTHRM_GRAPH_SHORTEST_PATH_WARSHALL_FLOYD_HPP_

#include <algorithm>
#include <iterator>
#include <vector>

namespace emthrm {

template <typename T>
struct WarshallFloyd {
  std::vector<std::vector<T>> graph, dist;

  WarshallFloyd(const std::vector<std::vector<T>>& graph, const T inf)
      : graph(graph), dist(graph), inf(inf), n(graph.size()),
        internal(n, std::vector<int>(n, -1)) {
    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] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            internal[i][j] = k;
          }
        }
      }
    }
  }

  void add(const int src, const int dst, const T cost) {
    srcs.emplace_back(src);
    dsts.emplace_back(dst);
    costs.emplace_back(cost);
  }

  void calc() {
    const int m = srcs.size();
    for (int i = 0; i < m; ++i) {
      graph[srcs[i]][dsts[i]] = std::min(graph[srcs[i]][dsts[i]], costs[i]);
      if (costs[i] <= dist[srcs[i]][dsts[i]]) {
        dist[srcs[i]][dsts[i]] = costs[i];
        internal[srcs[i]][dsts[i]] = -1;
      }
    }
    std::vector<int> vers(m * 2);
    std::copy(srcs.begin(), srcs.end(), vers.begin());
    std::copy(dsts.begin(), dsts.end(), std::next(vers.begin(), m));
    std::sort(vers.begin(), vers.end());
    vers.erase(std::unique(vers.begin(), vers.end()), vers.end());
    for (const int ver : vers) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (dist[i][j] > dist[i][ver] + dist[ver][j]) {
            dist[i][j] = dist[i][ver] + dist[ver][j];
            internal[i][j] = ver;
          }
        }
      }
    }
    srcs.clear();
    dsts.clear();
    costs.clear();
  }

  bool has_negative_cycle() const {
    for (int i = 0; i < n; ++i) {
      if (dist[i][i] < 0) return true;
    }
    return false;
  }

  std::vector<int> build_path(const int s, const int t) const {
    std::vector<int> res;
    if (dist[s][t] != inf) {
      build_path(s, t, &res);
      res.emplace_back(t);
    }
    return res;
  }

 private:
  const T inf;
  const int n;
  std::vector<int> srcs, dsts;
  std::vector<T> costs;
  std::vector<std::vector<int>> internal;

  void build_path(const int s, const int t, std::vector<int>* path) const {
    const int k = internal[s][t];
    if (k == -1) {
      (*path).emplace_back(s);
    } else {
      build_path(s, k, path);
      build_path(k, t, path);
    }
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_SHORTEST_PATH_WARSHALL_FLOYD_HPP_

#line 1 "include/emthrm/graph/shortest_path/warshall-floyd.hpp"



#include <algorithm>
#include <iterator>
#include <vector>

namespace emthrm {

template <typename T>
struct WarshallFloyd {
  std::vector<std::vector<T>> graph, dist;

  WarshallFloyd(const std::vector<std::vector<T>>& graph, const T inf)
      : graph(graph), dist(graph), inf(inf), n(graph.size()),
        internal(n, std::vector<int>(n, -1)) {
    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] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            internal[i][j] = k;
          }
        }
      }
    }
  }

  void add(const int src, const int dst, const T cost) {
    srcs.emplace_back(src);
    dsts.emplace_back(dst);
    costs.emplace_back(cost);
  }

  void calc() {
    const int m = srcs.size();
    for (int i = 0; i < m; ++i) {
      graph[srcs[i]][dsts[i]] = std::min(graph[srcs[i]][dsts[i]], costs[i]);
      if (costs[i] <= dist[srcs[i]][dsts[i]]) {
        dist[srcs[i]][dsts[i]] = costs[i];
        internal[srcs[i]][dsts[i]] = -1;
      }
    }
    std::vector<int> vers(m * 2);
    std::copy(srcs.begin(), srcs.end(), vers.begin());
    std::copy(dsts.begin(), dsts.end(), std::next(vers.begin(), m));
    std::sort(vers.begin(), vers.end());
    vers.erase(std::unique(vers.begin(), vers.end()), vers.end());
    for (const int ver : vers) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (dist[i][j] > dist[i][ver] + dist[ver][j]) {
            dist[i][j] = dist[i][ver] + dist[ver][j];
            internal[i][j] = ver;
          }
        }
      }
    }
    srcs.clear();
    dsts.clear();
    costs.clear();
  }

  bool has_negative_cycle() const {
    for (int i = 0; i < n; ++i) {
      if (dist[i][i] < 0) return true;
    }
    return false;
  }

  std::vector<int> build_path(const int s, const int t) const {
    std::vector<int> res;
    if (dist[s][t] != inf) {
      build_path(s, t, &res);
      res.emplace_back(t);
    }
    return res;
  }

 private:
  const T inf;
  const int n;
  std::vector<int> srcs, dsts;
  std::vector<T> costs;
  std::vector<std::vector<int>> internal;

  void build_path(const int s, const int t, std::vector<int>* path) const {
    const int k = internal[s][t];
    if (k == -1) {
      (*path).emplace_back(s);
    } else {
      build_path(s, k, path);
      build_path(k, t, path);
    }
  }
};

}  // namespace emthrm

Back to top page