グラフがダイクストラのアルゴリズムを適用するのに有効である、すなわち負のエッジ重みがないと考えてください。 Dijkstraのアルゴリズムは、各ラウンドの最小距離ノードが抽出されるように選択されている場合にのみ機能します。最小距離ノード以外を抽出するとダイクストラのアルゴリズムが失敗するという証拠は何になるでしょうか？ 私は良い議論を探していますが、サポートの例は大歓迎です。Dijkstraのアルゴリズムが各ラウンドでminを抽出することが必須であるのはなぜですか？
非最小ノードを抽出すると、抽出時に最短距離が分からなかったノードが抽出されます。後で計算されますが、ノードは再度抽出されないため、最後に少なくとも1つの間違った最小距離が残されます。
例：
あなたはそれを抽出するだけなので、あなたはこれを抽出し、d[1] = 0を持つことになります。
d[3] = 3
d[2] = 1
2を抽出する必要がありますが、あなたは
3を抽出しましょう：
これが設定されます。
d[4] = 4と設定します。
次に、2を抽出し、d[3] = 2と設定したとします。
次に、4のみが抽出されます。あなたはそれを抽出し、あなたは完了です。
d[4] = 3ではなく、d[4] = 4という間違った値が残っています。
これは、ノードを複数回抽出できないことを前提としています（これは、古典的Dijkstraのアルゴリズムでは不可能です）。あなたがこれを許せば、あなたが提案するものはうまくいくが、間違いなく効率的でもダイクストラのものでもない。