使用Dijkstra's將2的冪返回相同的最短路徑嗎？

我有一個圖G =（V，E），其中有兩個權重函數w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有邊緣權重都是獨一無二的。使用Dijkstra's將2的冪返回相同的最短路徑嗎？

在兩個權重函數下，Kruskal的算法將返回相同的最小生成樹。

我知道kruskal是貪婪的，會選擇最短/最低成本的路徑。既然它們是肯定的，只要沒有成本爲1.5或者更低的路徑，我們最終會選擇相同的MST。

在兩個權重函數下，Dijkstra的算法將返回相同的最短路徑。

我不確定這個。我認爲這也是事實，但我覺得如果我們得到足夠多的數字，一條路徑實際上可能會變得更大。任何人都可以證實，如果我們要冪的路徑長度？

不是。想象兩條路徑，一條路徑的權重爲1 + 2 + 3，另一條的權重爲4.現在計算每條邊的權重。

2017-09-22 15:28:07

這是爲了迪傑斯特拉的假設嗎？我們可以擁有比另一個更多邊緣的路徑嗎？我明白，以你的榜樣爲例，我們將有不同的最短路徑，但它們似乎是兩個不同的例子？ –

@Andrew Raleigh：我不明白你的問題。當然，你可以在兩個節點之間有多條路徑。如果只有一條路徑，找到最短路徑將是微不足道的。 –

我的意思是克魯斯卡爾的算法是否符合假設？我的意思是說，你選擇Djikstra的例子有4，這將是16.然後你給了另一個是1,2和3，這將是1,4和9.所以我沒有真的得到你的反例如何工作，對不起：（ –

回答