1. 概要

このチュートリアルでは、負の重みを持つグラフでDijkstraのアルゴリズムを使用するときに発生する問題について説明します。

まず、ダイクストラのアルゴリズムの背後にある考え方とその仕組みを思い出します。

次に、負の重みを持つグラフで、ダイクストラのアルゴリズムに関するいくつかの問題を示します。

2. ダイクストラのアルゴリズムを思い出してください

2.1. 本旨

からまでの番号が付けられたノードを含むグラフがあるとします。 さらに、これらのノードを接続するエッジがあります。 これらの各エッジには、このエッジを使用するためのコストを表す重みが関連付けられています。 ダイクストラのアルゴリズムは、特定のソースノードから特定のグラフ内の他のすべてのノードへの最短経路を提供します。

2つのノードとの間の最短パスは、との間のすべての可能なパスの中で最小のコストを持つパスであることを思い出してください。

2.2. 実装

実装を見てみましょう。

最初に、ソースノードと指定されたグラフ内の他のすべてのノード間の最短パスを格納するという配列を宣言します。 さらに、探索されたノードを格納し、コスト値に従って昇順でソートされた状態に保つ優先キューを宣言します。

次に、ソースノードを優先キューに追加し、ソースノードに到達するためのコストをに等しくします。これは、ノードからそれ自体への最短パスがゼロに等しいためです。 次に、キューがまだ空でない限り、複数のステップを実行します。 各ステップで、キューから最小コストのノードを取得します。 キューは各ノードのコストに基づいてソートされるため、コストが最小のノードが優先キューの先頭に配置されます。

その後、現在のノードの各ネイバーのコストが、新しく検出されたノードよりも優れているかどうかを確認します。 新しいコストは、現在のノードに到達するためのコストに、現在のノードを隣接ノードに接続するエッジの重みを加えたものに等しくなります。 新しいコストが低い場合は、現在のノードを経由して到達することにより、ソースノードからこのネイバーへの新しいパスを見つけました。 この場合、ネイバーのコストを更新し、優先キューに追加します。

最後に、ソースノードから指定されたグラフ内の他のすべてのノードへの最短パスを格納する配列を返します。

2.3. コンセプトの証明

ダイクストラのアルゴリズムの正しさの証明は、どのサブパスよりも短いパスがあった場合、パス全体を短くするために、そのサブパスをより短いパスで置き換える必要があるという貪欲な考えに基づいています。 この考えをよりよく説明しましょう。

ダイクストラのアルゴリズムの各ステップでは、これまでの最短パスがわかっています(キュー内の各ノードは、ソースからこのノードへの一意のパスを表します)。 ただし、これは、より多くのノードを探索すると、後のステップでより適切なパスを見つけることができることを意味します。 したがって、現在検出されているパスが最短パスであるかどうかを確認することはできません。

それでも、キュー内でコストが最も低いパスを1つだけ確認できます。 その理由は、他のパスの方がコストが高いためです。 したがって、最も低いコストでパスのエンドノードに到達するには、いくつかの追加のエッジを使用する必要があり、その結果、コストが高くなります。 したがって、常にコストが最も低いパスを選択し、このパスの次のノードを探索します。

私たちの仮定は、すべてのエッジが負ではない重みを持っているという考えに基づいていることに注意してください。 そうしないと、コストが最も低いパスを選択することについて確信が持てません。 その理由は、コストの高い別のパスを選択すると、そのパスからいくつかの負のコストのエッジを探索するときに、総コストが低くなる可能性があるためです。

次のセクションでは、一部のエッジのコストが負であるためにダイクストラのアルゴリズムで失敗する2つのケースについて説明します。

3. 無限サイクル

次のグラフを見てみましょう。

ソースノードを。 からダイクストラのアルゴリズムを実行する場合、優先度キューにとを追加します。どちらもコストは。です。

次に、優先キュー内のすべてのノードの中でコストが最小であるため、ノードをポップします。次に、コストが。に等しいノードとを追加します。 次のステップでは、ノードをポップし、ノードとを追加します。どちらもコストは。です。 次に、ノードに戻ります。

同じシナリオが繰り返し発生します。 ご覧のとおり、反復ごとにコストが低くなり、ダイクストラのアルゴリズムを使用してノードに到達することはないため、無限のサイクルでスタックします。

結論は、 グラフに少なくとも1つの負のサイクルが含まれている場合、ダイクストラのアルゴリズムは終了しません。 負のサイクルとは、エッジの総重みが負のサイクルを意味します。

4. 間違った道

次のグラフを見てみましょう。

ソースノードになります。 からダイクストラのアルゴリズムを実行する場合、コストがそれぞれとに等しい優先度キューにとを追加します。

次に、優先キュー内のすべてのノードの中でコストが最小であるノードをポップし、コストがに等しいノードを追加します。 最後に、ノードをポップすると、ダイクストラのアルゴリズムはここで停止します。

配列は次のようになります。これは、それぞれノード、、、およびに到達するための最短パスのコストを表します。 ただし、パスを介して等しいコストでノードに到達できます。

何が起こったのかというと、より少ないコストでノードに到達したために通過しなかったため、この貪欲なアプローチを使用して通過するすべてのパスを無視します。

このケースを結論付けるために、グラフに負のエッジが含まれているが負のサイクルが含まれていない場合、ダイクストラのアルゴリズムは終了する可能性があります。 ただし、間違った結果になる可能性があります。

5. 結論

この記事では、ダイクストラのアルゴリズムを思い出し、ネガティブエッジで失敗する2つのシナリオを提供しました。