下水道設計的最佳路徑

Question

是否有任何算法可以在給定的連接的無向加權圖/網絡中找到源和匯之間的所有路徑？該網絡由多個源節點和一個匯聚節點組成。路徑應該沒有循環

Answer 1

我會用一個A *算法來解決這個問題，其基本路徑發現存在以下差異。

• 從信宿而不是從源開始，因爲只有一個信宿
• 每個節點是一組位置，而不是一個單一的位置。在每次迭代中，將所有位置的鄰居添加到隊列中。還要爲所有鄰居創建分支，以便在下一個集合中再增加一個位置。將最大位置數限制爲來源數作爲優化。
• 跟蹤哪些源已在每個路徑到達
• 的行進成本函數應與所有分支路的總行駛距離合並
• 估計函數應結合所有剩餘的源

如果正確使用A *算法，這應該給出最佳路徑。

Answer 2

如果您尋找所有無迴路路徑，breadth-frist search應該完成這項工作。在迭代中，對於每個當前路徑，只要它到達路徑或接收器上已有的點，就不要繼續它。

Answer 3

它看起來類似於Minimum Spanning Tree。