如何記錄從源頂點到目標頂點的所有最短路徑

Question

我目前使用Boost圖庫的dijkstra算法http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html來計算一對頂點之間的最短距離路徑。到目前爲止，我只能獲得存儲在前趨映射中的最短路徑。

所以我的問題是：是否有可能讓函數返回一對頂點之間的所有可能的最短路徑？

Answer 1

不，你需要自己建立。一種方法是使用兩次調用Dijkstra來計算從源頂點s（G）到sink頂點t（即，轉置圖中距離t的距離）的距離。然後，提取包含這些節點u的子圖，使得距離（s，u）+距離（u，t）=距離（s，t）和那些弧uv，使得距離（s，u）+長度（u，v ）+ distance（v，t）= distance（s，t）並遞歸枚舉此子圖中的所有st路徑。