2
Greetings Overflowers，有沒有算法來計算最短的樹（不是路徑）？
我有一個加權有向圖，我想要最低成本的樹，覆蓋所有節點，其中根是圖的特定給定節點。我不知道我是否也可以在每個節點上設置不同的最大分支，從此節點到其他節點（外邊）的分支數目等於或小於最大值？
那麼，什麼是最合適的算法我需要開始閱讀？我希望這是足夠快:)
非常感謝！
A
回答
9
您正在尋找一個定向最小生成樹（arborescence），它是一個最佳分支。
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
相關問題
- 1. 最短路徑tsp算法
- 2. 最短路徑算法
- 3. Java：使用鄰接表來計算所有對最短路徑？
- 4. 最佳最短路徑算法
- 5. 最有效的最短路徑算法非負邊緣圖
- 6. AFP Dijkstra的最短路徑算法
- 7. Dijkstra的算法最短路徑
- 8. 尋找最短路徑數的算法
- 9. Floyd的最短路徑算法C++
- 10. 在android中的最短路徑算法
- 11. Dijkstra的最短路徑算法修改
- 12. JUNG中的樹圖（用於最短路徑算法）
- 13. 增量Dijkstra或最短路徑算法？
- 14. 調整到最短路徑算法
- 15. 最短路徑更快 - SPFA算法？
- 16. Floyd-Warshall算法：得到最短路徑
- 17. 最短路徑算法遞歸
- 18. 概率和最短路徑算法
- 19. Dijkstra的算法 - 只有負成本的DAG最短路徑
- 20. 算法：所有點之間的最短路徑
- 21. 有關最短路徑和這樣的算法問題
- 22. neo4j，如何在所有最短路徑算法中排除一些路徑
- 23. 如何計算BFS算法中的移動？ （在迷宮中的最短路徑）
- 24. 計算最長路徑
- 25. 有沒有算法來計算利薩如圖的面積？
- 26. 總是有一些MST是最短路徑樹嗎？
- 27. Dijkstra的算法不會生成最短路徑？
- 28. 如何限制最短路徑 - dijkstra算法的最大代價？
- 29. 最小路徑算法
- 30. 算法來計算兩個點之間的最短路徑的三維的表面上齧合
謝謝，這似乎是:)任何想法如何去關於最大分支限制？ – geeko 2011-05-28 15:07:01
@geeko，我不知道如何實現它的頭頂。我知道我的頭腦不是一個簡單的變化（你可以很容易地證明這一點）。但我沒有解決方案... – davin 2011-05-28 15:31:17