フロイド – ウォーシャル アルゴリズム: コーディング面接ガイド

TL;DR: フロイド – ウォーシャル アルゴリズムは、動的プログラミングを使用してすべてのペアの最短経路を計算します。グラフから距離行列を初期化し、すべての中間頂点 k について、各ペアを dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) で更新します。これは O(V³) 時間と O(V²) 空間で実行され、負の対角エントリを通じて負のサイクルを露呈する可能性があります。

フロイド・ウォーシャルアルゴリズムとは何ですか?

Floyd-Warshall は、すべての順序付き頂点ペア間の最短パスを求める動的プログラミング アルゴリズムです。これは、有向または無向の重み付きグラフで動作し、負のエッジを許可します。ただし、関連する負の重みサイクルが存在する場合、サイクルを繰り返し通過することでパス コストが削減され続けるため、一部の最短パスには有限の最小値が存在しません。

このアルゴリズムは、グローバル パスの問題を 1 つの決定に変えるため、記憶に残ります。つまり、現在の中間頂点 k について、i から j への最もよく知られているパスはそのままの方が良いのか、それとも i から k に進み、次に k から j に進む方が良いのかということです。

再発をどのように導き出すのでしょうか？

D(k, i, j) を、中間頂点が最初の k 個の頂点からのみ得られる i から j までの最短距離として定義します。許可された最短パスは、頂点 k を回避して D(k−1, i, j) を維持するか、k を使用して i から k までの最良の許可されたパスと k から j までの最良の許可されたパスに分割します。

これにより、次の繰り返しが得られます。

YTOKEN0

ステージ k は互換性のある方法でステージ k-1 の値のみに依存するため、行列を適切な場所で更新できます。この推論は、重要なループ順序も説明しています。k は最も外側のループでなければなりません。 i または j を外側に置くと不変式が変更され、部分的に許可されたパスが誤って使用される可能性があります。

距離行列を初期化するにはどうすればよいでしょうか?

V × V 行列を作成します。 dist[i][i] をゼロに設定し、ダイレクト エッジのセルをその重みに設定し、ダイレクト エッジが存在しない場合は無限大を使用します。平行なエッジが可能な場合は、直接の重みを最小に保ちます。 2 つの距離を追加する前に、無限センチネルがオーバーフローしたり、誤った候補が作成されたりしないように、両方が有限であることを確認してください。

インタビューでフロイド＝ウォーシャルをどのように追跡しますか？

マトリックスの行にソース、列に宛先としてラベルを付けます。初期行列を表示し、k を 1 つ選択して、代表的なセルを評価します。各セルについて、現在の値を k を通るルートと比較します。両方のセグメントが到達可能で、新しい合計が小さい場合にのみ更新します。

通常、大きな例ではすべての行列を描画する必要はありません。 1 つの改善と 1 つの変更されていない値を含む、不変条件を示すのに十分なセルをトレースします。 k を完了した後、中間頂点が処理されたセットに制限されているパスの中ですべての行列エントリが最適であることを示します。

どのような疑似コードを書けばよいでしょうか?

k を外側にした 3 つのネストされたループを使用します。

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

有限検査と数値型について説明します。大きな整数センチネルを持つ言語では、負の値に無限大を加算すると、有限であるかオーバーフローのように見えることがあります。ガードは正確性の一部であり、単なる実装の詳細ではありません。

時間と空間の複雑さは何ですか?

3 つのループは k、i、j のすべての組み合わせを検査するため、ランタイムは O(V³) になります。距離行列は O(V²) スペースを占有します。インプレース更新により 3 次元テーブルが回避され、パス再構築のためのネクストホップまたは先行マトリックスにより O(V²) 個のスペースが追加されます。

Floyd-Warshall は、実装がコンパクトで予測可能であるため、適度な密度のグラフにとって魅力的なことがよくあります。非負のエッジを持つ大規模な疎グラフの場合、各ソースからダイクストラを実行する方が効率的になる可能性があります。選択する前に、必要な出力、グラフ密度、重み制約、頂点数を常に比較してください。

実際の最短経路をどのように再構築するのでしょうか?

距離だけでは頂点のシーケンスはわかりません。 i から j への直接エッジが存在する場合、j に初期化された next[i][j] 行列を維持します。 k を介したルーティングによって dist[i][j] が改善されるたびに、next[i][j] を next[i][k] に設定します。パスを再構築するには、目的地に到達するまで現在の頂点から next[current][destination] への移動を繰り返します。

再構築前に到達不能なペアをチェックし、負のサイクルのケースから保護します。ペアが負のサイクルに移動して目的地に到達できる場合、再構築するための有限の最短経路はありません。

フロイド・ウォーシャルはどのようにして負のサイクルを検出するのでしょうか?

アルゴリズムが終了したら、対角線を検査します。値 dist[v][v] < 0 は、負の重みサイクルが v から到達可能であり、v に戻ることができることを証明します。これは、単に負のエッジを見つけるよりも強力です。負のエッジは、完全に有効な最短パスを持つグラフに存在する可能性があります。

インタビュアーがどのペアが影響を受けるかを尋ねたら、i がそのような頂点 v に到達でき、v が j に到達できるすべての i と j を特定します。これらのペアは負のサイクルを任意に何度でもループできるため、最短パスの値は有限ではありません。

別の最短パス アルゴリズムを選択する必要があるのはどのような場合ですか?

重み付けされていないグラフには幅優先探索を使用し、非負の重みを持つ単一ソース問題にはダイクストラを使用し、負の重みまたは到達可能な負のサイクル検出が重要な場合には単一ソースにベルマン・フォードを使用します。すべてのペアの距離が必要であり、立法時間が許容できる場合には、フロイド – ウォーシャルが直接の選択肢となります。

避けるべき面接の間違いはどれですか?

k を別のループ内に入れたり、対角のゼロを忘れたり、ガードなしで無限を追加したり、負のエッジと負のサイクルを混同したり、O(V²) 行列空間にすべての表現で入力が自動的に含まれると主張したりしないでください。グラフに方向があるかどうか、平行なエッジが存在するかどうか、面接官が距離、パス、またはサイクルの影響を受けるペアを必要としているかどうかを明確にします。

コーディング インタビュー アシスタント ワークフロー を練習し、ベルマン-フォード アルゴリズム を比較し、ビッグ オーの複雑さに関するチートシート を確認してください。

よくある質問

ループだけでなく、不変条件も練習しましょう

YesToTheOffer は、コーディングの説明を構造化し、個人的な準備ノートに基礎を置き、特殊なケースを検討し、後で確認できるようにインタビューの記録を保存するのに役立ちます。