私の質問は、whileループのアルゴリズムのすべてのステップでQのすべてのvの最小値[v]を選択することが重要なのはなぜですか？ ？Dijkstraアルゴリズムのプロパティ
私はそれを見て、すべてのエッジ（u、v）は幅広い一次で緩和するつもりです（-s-> u-> vと（s、v） （u、v））、 だから、いつも最小のd [v]を選ぶことが重要なのはなぜですか？
は、それが最大dを有するように、頂点vを返す関数extractMaxFiniteD（Q）が存在すると仮定[V]すなわち
我々はU < -extractMaxFiniteD（Q）へのラインを変更すると仮定することができますQで有限です。誰かが私にグラフを描くことができます。このグラフでは、変更されたalgが失敗するか、またはそれより優れていますか？
私はこの質問がかなり難解で抽象的かもしれないことは知っていますが、some1がそれで私を助けることができれば素晴らしいでしょう。
例：
ノード：A、B、
エッジ（及び重り）C：（B、1）（C、10）（B、C、1）
あなたのアルゴリズムを試してみてください。あなたは、Cへの最小コスト経路が明らかに10であることを見いだすでしょう。
Qからノードを削除すると、あなたはそれを再び緩和しません。最大コストのノードを削除すると、そのノードに到達するためのより少ない経験的方法を考慮する。
Qから最小ノードを選択したくない場合はQから削除することはできません。将来の反復で緩和できるように、セット内に保持する必要があります。これは基本的にbellman-fordアルゴリズムの機能です。
Dijkstraのアルゴリズムの主な考え方は、頂点をQから取り除くと、この頂点は良好です。あなたはfututreでそれをリラックスする必要はありません。
あなたはQからランダムな要素を取る場合は、この条件が成立していない - あなたはQのうち、頂点vを取ったら、d[v]が実際vへの最短経路である保証するものではありません。
あなたは最小限取る場合 - あなたはd[v]
美しい答え、ありがとう。 –
@OfekRon：どうぞよろしくお願いいたします。それは素敵な質問だった:) – amit
は実際にあなたをした改善することはできません -
vがQに最小限である場合、Qの各u、d[u] >= d[v]、あなたが次に何をrelexationsので、どんなにのためにあるため、それが保証されているがどんなグラフでも試してみてください。 Maxを使用して不正確な結果が得られる確率は非常に高いです！ –私は特定のグラフでintrestedの方が少ないので、最小限のステップを選択することによって、どのプロパティが保持しようとしているのかを知りたい。 –
ほとんどすべてのグラフでこれを行うと、段階的に進み、中間結果を見ると、 –