從另一個

Question

不同最小生成樹假設我們給出

無向圖g，每一個節點i，1 < = I < n被連接到所有的j，我<Ĵ< = N

和一個來源s。

我們想找到最低最小生成樹認爲，從s（即從MST運行拘謹/ Dijkstra算法獲得的最小距離樹不同的總成本（定義爲所有邊權重的總和）在s上）至少一個邊緣。

解決此問題的最佳方法是什麼？因爲目前，我只能認爲某種固定點上(g,s)迭代

1. 運行Dijkstra算法來獲得參考圖r，我們需要從
2. costs := sum(edge_weights_of(r))
3. change := 0
4. 差異，每個頂點的u in r，爲從u到v的路徑上的每個到達頂點v運行一個bfs和note。
5. 迭代通過所有邊緣e = (a,b)在g：找到e'=(a',b')不在r並最大限度地減少newchange := weight(e') - weight(longest_edge(a',b'))
6. 如果（first_time_here OR newchange < 0）然後change += newchange
7. 如果（newchange < 0）goto 4
8. result := costs + change

這似乎浪費了很多時間......它依賴於添加邊緣t o生成樹創建一個循環，我們可以從中刪除最長的邊。

我也考慮過使用Kruskal來獲得一個總體最小生成樹，並且只使用上面的算法來替換單個邊，當來自prim和kruskal的樹碰巧是相同的，但這似乎不是作爲結果將高度依賴於在克魯斯卡爾運行期間選擇的邊緣。

任何建議/提示？

Answer 1

可以使用Prim`s算法

Prim's algorithm: 
let T be a single vertex x 
while (T has fewer than n vertices) 
{ 
    1.find the smallest edge connecting T to G-T 
    2.add it to T 
} 

現在，讓我們修改它做到這一點。

讓你有一個最小生成樹。說樹（E，V）
使用這種算法

Prim's algorithm (Modified): 
let T be a single vertex 
let isOther = false 
while (T has fewer than n vertices) 
{ 
    1.find the smallest edge (say e) connecting T to G-T 
    2.If more than one edge is found, { 
     check which one you have in E(Tree) 
     choose one different from this 
     add it to T 
     set isOther = true 
     } 
     else if one vertex is found { 
     add it to T 
     If E(Tree) doesn`t contain this edge, set isOther = true 
     Else don`t touch isOther (keep value). 
     } 
} 
If isOther = true, it means you have found another tree different from Tree(E,V) and it is T, 
Else graph have single minimum spanning tree