Dijkstra算法問題

如何將Dijkstra算法應用於圖來找到MST，使得生成的樹必須在兩個給定頂點之間有一條邊？（例如：MST必須包括X和Y之間的邊緣）Dijkstra算法問題

感謝

2011-06-01 coder9

Dijkstra找不到MST。 – Waldheinz 2011-06-01 14:13:03

是的。它需要在這種情況下被修改 – coder9 2011-06-02 00:53:33

檢查這[問題]（http://stackoverflow.com/questions/1909281/use-dijkstras-to-find-a-minimum-spanning-tree） – 2011-06-01 14:11:26

Dijkstra算法爲最短路徑（不MST），但類似於Dijkstra算法的東西，如修改，以找到一個最小生成樹，是稱爲Prim算法。 Prim的算法保持一個增長的樹，直到它橫跨整個圖。這裏引入的額外約束並不會造成太大的困難：您只需從X-Y開始，作爲您的樹。

具體來說，假設你的MST必須包含邊（X，Y）（如果有多個這樣的邊選擇最小權重），那麼從你的樹開始，有兩個節點X和Y以及它們之間的邊。現在，在每一步選擇最小邊（u，v），其中u在樹中，v在外部，將節點v和邊（u，v）添加到樹中，然後重複。

來源

2011-06-01 14:18:56 ShreevatsaR

+1爲Prim的算法，非常有趣http://en.wikipedia.org/wiki/Prim%27s_algorithm – 2011-06-01 14:51:12

我可以在Prim's中簡單地做到這一點，但問題是與使用Dijkstra找到MST與提到的限制 – coder9 2011-06-02 01:06:16

Dijkstra不會找到你一個MST。考慮三條邊的簡單圖形，AB成本4，BC成本5和AC成本7. Dikjstra總是希望選擇AB和AC作爲AC的最短路徑7，但總樹權重爲12.但是Prim的意志總是選擇AB和BC，因爲樹的總重量是9，儘管從A到C的最短路徑也是9.算法非常相似，但我永遠不會調用與後來的Dijkstra相似的東西。如果這是一項家庭作業，也許教授只是想讓你意識到Dijkstra是否容易進入Prim的算法？ – 2011-06-02 01:18:45

Dijkstra算法問題

回答

相關問題