最短路徑和最小生成樹的組合

我試過做無向加權圖的最小生成樹。但是，我需要找到一對或多對節點之間的最短路徑。之後，我必須找到圖的最小生成樹。我已經找到了必要節點之間的最短路徑，但我不知道如何找到包含這些最短路徑的最小生成樹。讓我舉個例子。最短路徑和最小生成樹的組合

G 
|2 
H  A 
|1  |6  
F  ------B 
|1   | 7 
E -----D-----C 
    2  8

A和E之間還有一個邊，有2個重量但我無法顯示它。

現在，首先我需要找到A和E之間的最短路徑（我必須這樣做是因爲我的應用程序），它是A-E-D-C，然後用最小跨度連接所有圖形。有沒有人幫助我提供一些線索？對不起，我英語不好它不是我的母語

來源

2013-12-22 caesar

與論壇網站不同，我們不使用「謝謝」或「任何幫助表示讚賞」，或在[so]上簽名。請參見「[應‘你好’，‘謝謝’標語，並稱呼從撤職？]（http://meta.stackexchange.com/questions/2950/should-hi-thanks-taglines-and-salutations-be -removed - 從 - 個）。 –

只是一個MST

如果你只是想在MST，這只是涉及到運行Kruskal's algorithm（見下文）或Prim's algorithm：

初始化一個單一頂點的樹，從圖中任意選擇。

將樹擴大一個邊：在將樹連接到樹中尚未存在的頂點的邊中，找到最小權重邊，並將其轉移到樹中。

重複步驟2（直到所有頂點都在樹中）。

這並不涉及獲取頂點之間的最短路徑。事實上，它不一定包含一些最短的路徑。考慮：

A 
1 |\ 
    B \ 
1 | \ 2 
    C \ 
1 | \ 
    D-----E 
    1

A和E之間的最短路徑是2（只是從A至E直接地），但MST（A-B-C-d-E）不包括邊緣。

「MST」包括一些最短路徑

如果你想找到MST包括一些最短路徑，這是一個最有趣的問題。

這可以通過運行克魯斯卡爾算法的一個小變化來解決。

從Wikipedia衍生：

創建林F（一組的樹木），其中圖中的每個頂點是一個單獨的樹，不包括從最短路徑的頂點。
爲一棵樹添加的最短路徑森林
創建一個包含所有在圖中不包括的最短路徑邊緣上的邊緣的集合S
雖然S是爲非空和F還沒有跨越
- 選自S
- 刪除以最小的重量的邊緣如果邊連接兩個不同的樹，然後將其添加到森林裏，兩棵樹合併爲一棵樹
- 否則丟棄邊緣

來源

2013-12-22 12:00:52 Dukeling

最短路徑和最小生成樹的組合

回答

相關問題