Floyd Warshall Algorithm
ノード数が n の有向グラフが与えられます。ノードには 0 から n-1 まで番号が付けられており、グラフは n 行 n 列の行列で表されます。matrix[i][j] はノード i からノード j への辺の重みを表し、辺がない場合は -1 です。また、matrix[i][i] は 0 です。経路の長さは、経路上の辺の重みの合計です。
ノード i からノード j までの最短経路の長さを [i][j] の要素とする n 行 n 列の行列を返してください。ノード i からノード j に到達できない場合は、[i][j] の要素を -1 とします。
関数
- matrixinteger-2d-array
- 辺の重み: matrix[i][j] は i から j への辺の重みを表し、辺がない場合は -1 です
- 戻り値integer-2d-array
- ノードの各ペア間の最短距離。経路がない場合は -1
制約
1 ≤ n ≤ 100、ここでn = matrix.length = matrix[i].lengthmatrix[i][i] = 0-
i ≠ jの場合、matrix[i][j]は-1（辺なし）または0 ≤ matrix[i][j] ≤ 1000です。 - 辺は一方向です。
matrix[i][j]とmatrix[j][i]は独立しています。
例
- 入力
- matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
- 出力
- [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
- 説明
- ノード1を経由すると、ノード0はノード2に11ではなく6で到達し、ノード3には9で到達します。ノード1はノード2を経由してノード0に3で到達します。ノード3からは何も出ていかないため、対角成分以外の行の値は-1です。
- 入力
- matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
- 出力
- [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
- 説明
- 2 から 1 への辺の重みは 0 なので、
0 → 2 → 1のコストは 1 となり、直接進む場合の 6 より小さくなります。ノード 1 から出る辺も、ノード 0 に入る辺もないため、それらの組み合わせは -1 のままです。
発展問題
テーブルを作成した後、1つの辺のコストが下がります。O(n³) のループをもう一度実行する代わりに、O(n²) で距離をすべて更新できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
経路が途中で立ち寄れるノード数に上限を設けます。立ち寄りが許可されない場合、最短経路は辺そのものなので、答えは行列から始まります。立ち寄り先としてノードをもう1つ許可すると、何が変わるでしょうか？
- ノード
kを、ノード0からk-1に加えて経由地点として使用できるようにします。iからjへの最短経路は、kを経由しない（その経路はすでに分かっています）か、kを一度経由します。後者は、iからkへの経路に、kからjへの経路を続けたもので、どちらもそれ以前の経由地点だけを使用します。 外側のループで
kを0からn-1まで回し、内側でiとjを回します。dist[i][k]とdist[k][j]の両方が存在し、その合計がdist[i][j]より小さい場合は、その合計を格納します。-1は「経路なし」として扱い、決して加算する数値として扱わないでください。
解説
すべてのノードのペアについて、最短経路を求める必要があります。Floyd-Warshallは、1つの三重ループですべてのn²個の答えを見つけます。各ラウンドでは、経路が立ち寄れるノードを1つ増やし、ペアごとに1回比較します。これまでの最良の経路と、新しいノードを経由する経路を比較します。
変化がなくなるまで、すべてのルートを1辺ずつ延長します
正しいが、最大のテストでは終わらない
考え方
行列から始め、各パスで、すべての経路を辺1本分延長します。iからmへの経路に辺m → jを加えると、iからjへの経路になり、より短い場合に採用します。何も変化しないパスが現れるまで繰り返します。
p回のパスの後、辺の数が最大p+1本のすべての最短経路が見つかります。重みはどれも負ではないため、ループを含まず、辺の数が最大n-1本の最短経路が存在し、すべての距離が確定するとパスは終了します。ノードが100個の場合、1回のパスにかかるステップ数はn³ = 10^6で、最短経路が長い連鎖をなす場合は最大n回のパスが必要です。計算量はO(n⁴)で、最大10^8ステップです。
アルゴリズム
matrixをdistにコピーします。- すべての
i、m、jについて、dist[i][m]とmatrix[m][j]の両方が存在する場合、それらの合計を計算します。 dist[i][j]が -1 または合計より大きい場合、合計を格納し、このパスで変更があったことを記録します。- 変更がなくなるまでパスを繰り返し、その後
distを返します。
def shortestDistances(matrix):
n = len(matrix)
# dist starts as the routes of one edge; -1 means no route found yet.
dist = [row[:] for row in matrix]
changed = True
while changed:
changed = False
# One pass: a route from i that ends at m may grow by the edge m -> j.
for i in range(n):
for m in range(n):
if dist[i][m] == -1:
continue
for j in range(n):
edge = matrix[m][j]
if edge == -1:
continue
via = dist[i][m] + edge
if dist[i][j] == -1 or via < dist[i][j]:
dist[i][j] = via
changed = True
return distFloyd-Warshall：各ラウンドで経由地をもう1つ増やせるようにする
考え方
経路の両端の間で、経路が停止できるノードを制限します。表は、停止箇所のない経路を表す行列から始まります。ラウンド k の後、dist[i][j] は停止箇所がノード 0 から k の間にすべて含まれる最短経路を表し、最後のラウンドで答えが得られます。
ラウンド k では、k にも停止できる最良の経路は、k を経由しない場合（その値はすでに表にあります）か、重みが負ではないため k を一度だけ経由する場合のいずれかです。経路の2つの区間は、ノード 0 から k-1 までのノードにしか停止しないため、それぞれ dist[i][k] と dist[k][j] になります。
最初の例では、ラウンド1でノード0からノード2への直接経路11が6に置き換わります。ラウンド2では、ノード0からノード3までの距離が6 + 3 = 9になります。この経路では、距離6の区間内でノード1に停止します。
表は1つで十分です。dist[k][k] が0であるため、ラウンド k では行 k と列 k は変化しません。
アルゴリズム
matrixをdistにコピーします。-1 はまだ経路が見つかっていないことを意味します。kを0からn-1まで動かし、すべてのiとjについて、dist[i][k]またはdist[k][j]が -1 なら、その組み合わせをスキップします。- それ以外の場合は、
via = dist[i][k] + dist[k][j]を計算します。 dist[i][j]が -1 であるか、viaより大きい場合は、viaを設定します。distを返します。
def shortestDistances(matrix):
n = len(matrix)
# dist starts as the direct edges; -1 means no route found yet.
dist = [row[:] for row in matrix]
# After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
for k in range(n):
for i in range(n):
if dist[i][k] == -1:
continue
for j in range(n):
if dist[k][j] == -1:
continue
via = dist[i][k] + dist[k][j]
if dist[i][j] == -1 or via < dist[i][j]:
dist[i][j] = via
return dist
落とし穴と境界ケース
- 重みとして -1 を加算すること:
-1 + 5 = 4は経路のように見えます。まず両方の部分を確認し、dist[i][j]の -1 はどの経路よりも悪いものとして扱ってください。 kのループを内側に置くこと。停止地点0からk-1を経由する経路は、ノードkを候補にする前に確定していなければなりません。- 最大の int を無限大として使うこと: 2つを加算すると、32ビット int ではオーバーフローして負の距離になります。実際の距離は最大でも 99 × 1000 = 99,000 なので、2 × 10^9 は 2^31-1 未満であることから、10^9 なら安全です。
- 辺が双方向だと思い込むこと。2つ目の例では、ノード 0 からノード 1 へ到達できますが、ノード 1 からはどこにも到達できません。
- 重みを無視する幅優先探索を実行すること: 1つ目の例では、ノード 0 からノード 2 までの距離として 6 ではなく 11 が報告されます。
よくある質問3
Floyd Warshall アルゴリズムの時間計算量はどれくらいですか？
n 個のノードに対して時間計算量は O(n³) です。ノードを対象とする3重の入れ子ループがあり、各ステップで加算と比較を1回ずつ行います。100個のノードでは10^6ステップです。距離テーブルの空間計算量は O(n²) で、インプレースで更新できます。
Floyd Warshall は負の辺の重みで動作しますか？
はい、重みの合計が0未満になるループである負のサイクルがなければ、そのとおりです。負のサイクルがある場合、最短経路は定義されず、表にもそのことが示されています。一部の dist[i][i] が0未満になります。
ダイクストラ法の代わりにフロイド・ワーシャル法を使うべきなのは、どのような場合ですか？
数百個程度までのノードを持つ密なグラフで、すべてのノードのペアに対して Floyd-Warshall を使います。すべてのノードから Dijkstra を実行する場合、配列では O(n³)、ヒープでは O(n · E log n) のコストがかかるため、大規模で疎なグラフではこちらが有利です。Floyd-Warshall はヒープを必要とせず、負の辺も扱えますが、Dijkstra は扱えません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def shortestDistances(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
期待される出力
[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]