「アルゴリズムの概要、第3版」の演習24.3-5では、これが間違っている（常に正しいとは限らない）例が必要です。それは可能ですか？私の考えでは、現在の頂点へのパスがすでに決定されているときにすべてのエッジが緩和されるため、これは不可能です。
一言一言：
N教授は、ダイクストラのアルゴリズムが正しいことを証明していると主張しています。彼は、ダイクストラのアルゴリズムは、グラフ内のすべての最短パスのエッジを、パスに表示される順序で緩和するため、パス緩和プロパティは、ソースから到達可能なすべての頂点に適用されると主張しています。ダイクストラのアルゴリズムが最短経路のエッジを順不同に緩和できる有向グラフを作成して、教授が間違っていることを示します。
次の有向グラフを考えてみましょう:(A,B),(A,C),(B,D),(C,D), (D,E)エッジの重み w(A,B)=1,w(A ,C)=1,w(B,D)=0,w(C,D)=0, w(D,E)=1. ソース頂点は A. ダイクストラのアルゴリズムで緩和されたエッジの可能な順列は次のとおりです。 (A、B)、(A、C)、(B、D)、(D、E)、(C、D)。また、ダイクストラのアルゴリズムを実行すると、Ad=0、Bd=1、Cd=1、Dd=1、Ed=2 になります。A から E への最短経路は 2 つあり、1 つは ABDE で、もう 1 つは ACDE です。矛盾は 2 番目のパスにあり、エッジ (C,D) は常に (D,E) の前に緩和されます。
言葉遣いのキー フレーズは、ダイクストラのアルゴリズムが「グラフ内のすべての最短パスのエッジを緩和する...」ということだと思います。
同じコストの最短経路が複数あるとしたら、それだけでは嘘です。
次のグラフを考えてみましょう: A -> B、A -> C、B -> D、C -> D。ソースは A で、宛先は D です。すべてのエッジの重みは 1 です。A から D への 2 つのパスがあり、1 つは B を通ります。ただし、一方のエッジ B->D または C->D は緩和されません。
他のエッジを D に評価する前にダイクストラが終了するため、まだ納得できませんか? 追加のエッジ D->E を投入し、Destination を E に設定します。A->D から B を通るパスは、A->D から C を通るパスと同じコストであり、どちらも A->E からのコストよりも安価です。ただし、アルゴリズムは、最短パスがまだわかっていない頂点へのエッジのみを緩和するため、2 番目のエッジを D に緩和することはありません。
ポイントは、前提から結論が導かれないことと、反例を構築することです。SSSP はすべての最短パスを見つけます。最短パスを厳密な順序で見つける必要がある理由はありません。ツリーグラフを考えてみましょう。すべてのパスも最短です。ここで、ルートを緩和すると、エッジに特定の順序付けはありません。しかし、あなたがそれを課したとしましょう。次に、最も近い非ルート ノードを緩和した後、2 番目の層への非常に長いエッジがたくさんある可能性があります。次に近いルートネイバーには、2 番目の層のその部分への非常に短いアウトバウンド エッジがたくさんある可能性があります。その場合、パスの合計の長さに寄与するエッジを、既に緩和した他のエッジよりも短く緩和します。これは、エッジではなく常にNODESを最短パスの順序で緩和するためです。
グラフを考えてみましょう:
A--->B A--->C B--->C C--->D
すべてのエッジの重みを 0 にします。
ダイクストラのアルゴリズムは、次の順序でエッジを緩和できます
(A,C) (A,B) (C,D) (B,C)
グラフには、A から D への 2 つの最短パスがあり、どちらもコストは 0 です。
A-->B-->C-->D or A-->C-->D
最短経路 {A-->B-->C-->D} のエッジは、(B,C) が (C,D) 後に緩和されるため、順不同で緩和されます。
宛先に到達する単一のエッジ、重み 3 を生成します。ここで、複数のストップで構成され、合計重量が 3 未満で、目的地に到達するパスを追加します。原点を緩和すると、宛先ノードが 3 つに色分けされますが、これは誤りです。そのセットが空になるまで、(宛先への最小既知パス) よりも近いすべてのノードを緩和し続ける必要があります。そうして初めて、D のアルゴリズムが正しい答えを与えたことを確信できます。
もっと楽しみたい場合は、A* アルゴリズムを調べてください。