私は、ダイクストラとプリムのアルゴリズムが、複数の頂点から移動先を選択しているときに何が起こるのか疑問に思っていました。同じ重みを持つ複数の頂点があります。
例えば
4357 次
4 に答える
4
複数の MST が存在する可能性があり、任意のタイブレーク ルールを使用すると、別のタイブレーク ルールが得られる可能性がありますが、それでも MST になります。
たとえば、すべての辺の重みが 1 である三角形 ABC を想像できます。この場合、3 つの MST があり、それらはすべて最小です。
同じことがダイクストラと最短パス スパニング ツリーにも当てはまります。複数の最短パス スパニング ツリーが存在する可能性があります。
于 2010-04-28T15:28:42.433 に答える
4
それは問題ではありません。通常、どちらのノードが優先キューに最初に追加されたかなど、任意の方法で引き分けになります。
ダイクストラの目標は、最短経路を見つけることです。すべての最短経路を見つけたい場合は、同順位について心配する必要があります。
于 2010-04-28T15:26:49.157 に答える
0
間違っている場合は訂正してください。ただし、ダイクストラのアルゴリズムを適用するための代替パスがグラフにありません。
于 2010-04-28T15:27:43.570 に答える
-1
ダイクストラ アルゴリズムは、接触からすべてのエッジを展開 (または「緩和」) しますが、展開されていないノード (または「グレー」ノード) は最小のコストで展開します。
2 つのノードのコストが同じ場合、それはランダムです :)
于 2010-04-28T15:27:58.433 に答える