C++: Froyd-Warshall Algorithm

C++: ワーシャルフロイド法の実装

アルゴリズム解説：
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

コード：

// Froyd-Warshall Algorithm: O(|V| ^ 3)
template <typename T=int>
class FroydWarshall {
public:
  FroydWarshall(int num_nodes, T infinite=1000000001)
      : num_nodes_(num_nodes), infinite_(infinite) {
    data_ = std::vector<std::vector<T> >(
        num_nodes_, std::vector<T>(num_nodes, infinite_));
    for (int i = 0; i < num_nodes_; ++i) { data_[i][i] = 0; }
  }
  void MakeEdge(int from, int to, T weight) {
    data_[from][to] = weight;
  }
  void Update() {
    for (int k = 0; k < num_nodes_; ++k) {
      for (int i = 0; i < num_nodes_; ++i) {
        for (int j = 0; j < num_nodes_; ++j) {
          data_[i][j] = std::min(data_[i][j], data_[i][k] + data_[k][j]);
        }
      }
    }
  }
  bool IsReachable(int from, int to) { return data_[from][to] != infinite_; }
  std::vector<T> operator[](int from) { return data_[from]; }

private:
  std::vector<std::vector<T> > data_;
  int num_nodes_;
  T infinite_;
};

使用方法：

FroydWarshall<> g(100);
g.MakeEdge(0, 1, 10);
g.MakeEdge(1, 3, 20);
g.Update();  // must do this to calculate
std::cout << g.IsReachable(0, 2) << std::endl;  // print "0": cannot reach this vertex
std::cout << g.IsReachable(0, 3) << std::endl;  // print "1": can reach
std::cout << g[0][3] << std::endl;  // print "30": shortest path from vertex[0] to vertex[3]