2の累乗を持つパスは、Dijkstraを使用して同じ最短パスを返しますか？

私は、2つの重み関数w1（e）およびw2（e）を有するグラフG =（V、E）を有しており、 w1（e）=（w2（e））^ 2である。すべてのエッジウェイトはユニークでポジティブです。2の累乗を持つパスは、Dijkstraを使用して同じ最短パスを返しますか？

両方の重み関数の下で、Kruskalのアルゴリズムは同じ最小スパニングツリーを返します。

私は、kruskalが欲張りであり、最短/最低コストのパスを選択することを知っています。彼らは肯定的なので、1.5以上のコストがかからない限り、同じMSTを選択することになります。

両方の重み関数の下で、ダイクストラのアルゴリズムは、同じ最短経路を返します。

これはわかりません。私はそれもまた真実だと思うが、十分な数の数字が得られれば、実際には1つの経路が大きくなるかもしれないように感じる。パスの長さを累乗すると誰でも確認できますか？

いいえ1つのウェイトがウェイト1 + 2 + 3で、ウェイトが1である2つのパスを想像してください。4.すべてのエッジのウェイトを四角にします。

2017-09-22 15:28:07

これはダイクストラの前提ですか？他のエッジよりもエッジが多いパスを使用できますか？私は、あなたの例では最短の道が異なると思っていますが、2つの異なる例のようです。 –

@Andrewローリー：私はあなたの質問を理解していません。もちろん、2つのノード間に複数のパスを設定することもできます。パスが1つしかない場合は、最短パスを見つけることは簡単です。 –

私はKruskalのアルゴリズムが前提を保持しているのでしょうか？そして、私はちょうどDjikstraの例題を4にすることを選択しました。それは16となります。そして1,2、そして3を1,4、そして9にします。そうではありません実際にあなたの反例がどのように働くかを知っています。（ –

答えて