Warshall Floyd (全頂点対最短経路)
(graph/warshallFloyd.hpp)

• View this file on GitHub
• Last update: 2022-07-12 12:30:29+09:00
• Include: #include "graph/warshallFloyd.hpp"

• $O(N^3)$で任意の2頂点の最短経路を求める。
• 動的計画法で実装されている。
• 木の場合はLCAを使えばクエリごとに$O(\log V)$で求められるので検討する。
• 辺が少なければ、全ての頂点でダイクストラ$(O(E\log V))$を検討する。

Verified with

• test/graph/warshallFloyd.aoj_GRL_1_C.test.cpp

Code

#pragma once
#include<vector>
#include<limits>
using namespace std;

template <typename T>
void warshall_floyd(vector<vector<T>> & dp){
  // dpは隣接行列。dp[i][i] = 0である
  // 結果のdp[i][i]に負が入っていたら負の閉路が存在する。
  T INF = numeric_limits<T>::max();
  for(size_t k=0; k<dp.size(); k++){
    for(size_t i=0; i<dp.size(); i++){
      for(size_t j=0; j<dp.size(); j++){
        if(dp[i][k] == INF || dp[k][j] == INF) continue;
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
      }
    }
  }
}

#line 2 "graph/warshallFloyd.hpp"
#include<vector>
#include<limits>
using namespace std;

template <typename T>
void warshall_floyd(vector<vector<T>> & dp){
  // dpは隣接行列。dp[i][i] = 0である
  // 結果のdp[i][i]に負が入っていたら負の閉路が存在する。
  T INF = numeric_limits<T>::max();
  for(size_t k=0; k<dp.size(); k++){
    for(size_t i=0; i<dp.size(); i++){
      for(size_t j=0; j<dp.size(); j++){
        if(dp[i][k] == INF || dp[k][j] == INF) continue;
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
      }
    }
  }
}

Back to top page