在加權循環有向圖中查找從源到目標的所有路徑

我試圖在邊有權重的有向圖中找到從源到目標的所有可能路徑。存在循環但不應導致無限循環。在加權循環有向圖中查找從源到目標的所有路徑

我已經使用了BFS，但無法檢測週期，因此我可以在路由中考慮它們。

例如我有以下鄰接列表：

'C':['D','E'] 
'D':['E','C'] 
'E':['B'] 
'B':['C']

對於源是「C」和目的地址爲「C」同樣，假設路徑應該不長於4點停止，我將具有以下路線爲結果：

CDC CEBC

來源

2015-12-09 don ali

如果使用DFS，則可以在遞歸調用期間將節點標記爲正在訪問，並在調用完成時取消標記它們。（或者在網絡x中使用[all_simple_paths]（https://networkx.github.io/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html））。 –

這僅用於檢測週期嗎？ –

當通過圖遍歷，而不是作爲訪問標記頂點，作爲嘗試訪問標記邊緣。

來源

2016-04-13 16:56:27

在加權循環有向圖中查找從源到目標的所有路徑

回答

相關問題