ベルマンフォード法

導入

単一始点最短経路問題によく使われるアルゴリズムです。
ダイクストラ法と一緒に紹介されることが多いです。
当時初めて触れた時なかなか理解できなかったのを覚えています。

両者の主な違いを並べておきます。

	ダイクストラ	ベルマンフォード
負の辺	不可	可
負の閉路検出	不可	可
計算量	$O(E\log{V})$	$O(EV)$

上図の通りベルマンフォードでは負の辺を扱うことができます。凄いですね。

仕組み

本題に入る前に、グラフの最短経路上の任意の部分路は最短路であるという性質を知っている必要があります。

例えばA → B → C → Dが最短経路であるならば、その部分路であるA → B → CやB → C → Dもそれぞれ最短経路であることが保証されます。
この性質は最適部分構造と呼ばれ、最短経路アルゴリズム全般の理論的な土台となっています。動的計画法（DP）における「部分問題の最適解が全体の最適解を構成する」という考え方と本質的に同じです。

ベルマンフォード法はこの性質を活用し、始点から辺1本で到達できる最短経路、辺2本で到達できる最短経路というように部分路の最短性を一段ずつ積み上げることで、最終的に全頂点への最短経路を確定させます。
最短経路に含まれる頂点の数は最大でもV-1個(始点を除く全ての頂点数)であることから、V-1回のループで全ての最短経路が確定することが保証されます。

そこから負閉路検出も自然に導けます。

V-1回のループが終わった後にもう1回緩和して、距離が更新される頂点があれば負閉路が存在することになります。
V-1回で全経路が確定しているはずなのに、さらに距離が縮まるということは「ぐるぐる回るほど距離が小さくなる閉路」つまり負閉路があるということです。

実装例

問題
$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺には重みがあり、負の重みも存在しうる。

頂点 $1$ （0-indexed では頂点 $0$ ）を始点として以下を求めよ。

負の閉路が存在するなら yes を出力せよ
存在しないなら no を出力し、続けて頂点 $1$ から各頂点への最短距離を空白区切りで出力せよ（到達> 不可能な頂点は $10^{18}$ を出力）

制約

$2 \le N \le 1000$

$1 \le M \le 10000$

$-10^9 \le W \le 10^9$

自己ループなし

辺は有向

入力形式
$N, M$
$U_1, V_1, W_1$
$U_2, V_2, W_2$
$. . .$
$U_M, V_M, W_M$

頂点番号は 0-indexed
辺は $U_i$ から $V_i$ へ重み $W_i$

出力形式
負の閉路あり
yes
負の閉路なし
no
0 距離1 距離2 ... 距離N-1

const long long INF=1e18;
int main(){
  int n,m;
  cin>>n>>m;
  vector<tuple<int,int,int>> edge(m);
  int u,v,w;
  for(int i=0;i<m;i++){
    cin>>u>>v>>w;
    edge[i]={w,u,v};
  }
  vector<long long> dist(n,INF);
  dist[0]=0;
  for(int i=0;i<n-1;i++){
    for(auto [cost,from,to]:edge) {
      if(dist[from] == INF) continue;
      dist[to]=min(dist[to], dist[from]+cost);
    }
  }
  bool judge=false;
  for(int i=0;i<1;i++){ //ループは1回でOK
    for(auto [cost,from,to]:edge) {
      if(dist[from] == INF) continue;
      if(dist[to] > dist[from]+cost){
        judge = true;
        break;
      }
    }
  }
  if(judge) cout<<"yes"<<endl;
  else{
    cout<<"no"<<endl;
    for(auto tmp:dist) cout<<tmp<<" ";
    cout<<endl;
  }
}