最短経路問題

ARC031のD問題解こうと思ったら二部グラフの最大流とか言われてうぇええんって感じなので、グラフについて調べつつ忘れないように書いていきます。

最短経路問題には3種類の解法があります。
1. ベルマンフォード法
2. ダイクストラ法
3. ワーシャルフロイド法

1.ベルマンフォード法

これは単一始点最短路用で、O(V×E)のアルゴリズムであり、負のcostがあっても、負の閉路(重みの総和が負になるような閉路)が存在しなければ使うことができます。スタート地点sからの最短距離を保持するようなd[MAX_V]を用意してあげて、d[s] = 0,それ以外をd[i] = INFとしてあげます。その後、
d[i] = min{d[j]+cost[j][i] | e(j, i) ∈ E}
というアルゴリズムで順次計算してあげれば答えが出ます。sにつながっているところから距離が少しずつ決まっていく感じですね。ただ、毎回毎回全ての辺を見ていくので無駄が多い気がします。

2.ダイクストラ法

これも単一始点最短路用で、O(E×logV)のアルゴリズムであり、負のcostがあると使えません。負のcostが使えない代わりに高速化した感じですね。ベルマンフォード法と同じで、スタート地点sからの最短距離を保持するようなd[MAX_V]を用意してあげて、d[s] = 0, それ以外をd[i] = INFとします。
まず、まだ使われていない頂点のうち、頂点sからの距離、つまりd[MAX_V]の値が最も小さいものを選び出します。そうしたらその頂点から他の頂点までで最短距離を更新します。O(V×V)のように見えますが、dの値が最も小さいものを選ぶときはpriority_queueが使えるのでlogオーダーにできます！やった！

3.ワーシャルフロイド法

これは全点対最短路用で、O(V^3)のアルゴリズムであり、負のcostがあっても使えます。
たった3行くらい書けるので良い！基本的な考えはdpです。頂点0〜kとi, jのみを使う場合のiからjへの最短経路をd[k+1][i][j]とします。それを0〜k-1とi, jのみを使う場合に帰着させます。頂点kを使う場合はd[k+1][i][j] = d[k][i][j]ですよね。じゃぁ頂点kを使わない場合はd[k-1][i][k]+d[k-1][k][j]ですね。分解しただけです。また、同じ配列を使いまわせるので、最終的な式は、
d[i][j] = min{d[i][j], d[i][k]+d[k][j]}
となります。

まぁ知ってはいたのですが、頭を整理してみたかっただけです笑