Bellman Ford アルゴリズム: コーディング面接ガイド

TL;DR: ベルマン フォード アルゴリズムは、一部のエッジが負の重みを持つ場合でも、重み付き有向グラフ内の単一ソースの最短パスを見つけます。ソース距離をゼロに初期化し、その他すべてを無限大に初期化し、すべてのエッジを V マイナス 1 回まで緩和し、追加のパスを 1 回実行します。さらなる改善は、到達可能な負の重みサイクルが存在することを証明します。

ベルマン フォード アルゴリズムとは何ですか?

Bellman Ford は、動的プログラミング スタイルの最短パス アルゴリズムです。最初の完全なパスの後、最もよく知られているパスは多くても 1 つのエッジを使用します。 2 番目以降は、最大 2 つのエッジ。単純なパスには最大でも V マイナス 1 個のエッジが含まれており、これによりループ数と正確性の議論の両方が説明されます。ダイクストラのアルゴリズムとは異なり、ベルマン フォードは非負のエッジの重みを想定しません。

エッジ緩和をどう説明しますか?

重み w を持つ u から v へのエッジの場合、緩和では distance[u] + w が distance[v] より小さいかどうかが尋ねられます。 u に到達可能な場合にのみ加算を実行します。候補の方が優れている場合は、 distance[v] を更新し、predecessor[v] を u に設定します。先行配列は距離に関してはオプションですが、これを使用すると実際のパスを再構築し、結果を明確に説明できます。

インタビューでベルマン・フォードをどのように追跡しますか？

小さなグラフを使用し、パスごとに 1 つの距離行を書き込みます。ソース A を 0 に設定し、他の頂点を無限遠に設定します。一貫した順序で完全なエッジ リストをスキャンし、各更新を記録します。パス全体に変更がない場合は、早めに停止します。到達可能な負のサイクルが存在しない場合、エッジの順序によって中間行は変更される可能性がありますが、最終的な正しい距離は変更できないことを明示してください。

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

距離配列と先行配列を作成し、フル エッジ スキャン V マイナス 1 回を繰り返します。早期終了には変更されたフラグを使用します。最後に、すべてのエッジをもう一度スキャンし、到達可能な距離がまだ改善できる場合は負のサイクルを報告します。実稼働コードでは、パスの合計を保持し、加算前に無限センチネルを保護できる数値型を選択します。

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

標準の隣接エッジ リストの実装は、V マイナス 1 パスと 1 つの検出パスのそれぞれで E エッジをスキャンできるため、O(VE) 時間で実行されます。距離と先行データに O(V) 補助スペースを使用します。早期停止により有利な入力は改善されますが、最悪の場合の限界は O(VE) のままです。

ディクストラの代わりにベルマン・フォードを選択する必要があるのはどのような場合ですか?

負のエッジ重みが許可される場合、またはインタビュアーが到達可能な負のサイクル検出を明示的に要求する場合は、Bellman Ford を選択します。エッジの重みがすべて非負であるグラフには、優先キューを備えたダイクストラを選択します。これは、通常、ダイクストラの方が高速であるためです。すべてのペアの最短パスの場合、最初にグラフの密度、負の重み、およびパスが必要か距離のみが必要かを明確にします。

どの間違いを避けるべきでしょうか?

到達不可能な頂点から気を緩めたり、負のエッジを負のサイクルと混同したり、すべての負のサイクルが結果を無効にするなどと主張しないでください。ソースから到達可能なサイクルのみがその最短パスに影響します。また、V マイナス 2 パスだけを実行したり、最後の検出パスをスキップしたり、先行パスを維持せずにパスを再構築したりすることも避けてください。

どうすれば説明の練習ができるでしょうか？

3 つのバージョン (30 秒の定義、2 分間の正しさの説明、完全な実装) を練習します。到達不可能な頂点、サイクルのない 1 つの負のエッジ、到達可能な負のサイクル、および早期に安定するグラフをテストします。これにより、記憶されたコードが真の理解から切り離されます。

AI を使用して、すでに理解している内容を整理し、説明をリハーサルし、パフォーマンスをレビューします。雇用主と評価プロバイダーの規則に従い、経験、数値、結果を決してでっち上げないでください。

AI 面接副操縦士ガイド、履歴書に基づく準備、面接後のレビュー ワークフロー に進みます。

よくある質問

台本ではなく証拠を使って練習する

YesToTheOffer では、履歴書、役割説明、個人的なメモに準備とリアルタイムの回答構造を盛り込み、面接後のレビューのために記録を保存できます。