最小生成樹和最短路徑

我被賦予一個問題，即表示：最小生成樹和最短路徑

給予連接有向圖具有整數權重（正面和負面），開發發現兩個頂點之間的最短路徑的算法。

我以爲我可以使用最小生成樹算法，如kruskal的，然後使用012jxstra的算法來表明，因爲在一個MST中，每個頂點只有一個包含邊緣，dijkstra的算法即使在負權重下也能工作。

這聽起來copasteic？

p.s.我無法證明MST包含有向圖的最短路徑，每個頂點都有。

2012-11-08 Jake B

考慮n> = 2的n維網格。與任何樹一樣，MST的葉子只有一條邊連接到它們。 n維網格上的一個點在n個不同方向上有n個相鄰點，因此MST不支持到相鄰點的所有可能的最短路徑。 – mcdowella

首先，你應該注意你的圖表不應該有任何負循環。

二，通常Dikstra不會使用負權重圖。

渴求，Bellman-Ford Algorithm可以用於尋找有向負權圖的最短路徑。

2012-11-08 03:41:35

最小生成樹的規定之一沒有圓圈。克魯斯卡爾的算法證明了這一點。但是，感謝鏈接 –

您可以使用Bellman-ford算法，而無需創建MST。我想這將是更快的解決方案 –

@ReCoNciLiaTiOn你混淆了初始圖形，也可能有負循環，以及你想要生成的生成樹，這是一棵樹，因此沒有循環。 –

我無法證明MST包含有向圖的最短路徑，對於每個頂點。

這是因爲它是錯誤的。以邊權爲2,3和4的三角形圖.MST僅包含權重2和3的邊，但最短路徑具有權重4，並且通過MST的路徑具有權重5.

鑑於此，在算法中嵌入最小生成樹似乎是一個壞主意。

2012-11-09 19:55:40 eh9

回答