我目前正在使用 Boost 图形库的 dijkstra 算法 http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html计算一对顶点之间的最短距离路径。至此，我只能获取前身 map 中存储的一条最短路径。
所以我的问题是:是否可以让函数返回一对顶点之间所有可能的最短路径？
最佳答案
不，您需要自己构建它。一种方法是使用对 Dijkstra 的两次调用来计算从源顶点 s(在 G 中)到汇点 t 的距离(即，到转置图中 t 的距离)。然后，提取一个子图，其中恰好包含满足距离(s, u) + 距离(u, t) = 距离(s, t) 的节点u 和满足距离(s, u) + 长度(u, v) 的弧uv ) + distance(v, t) = distance(s, t) 递归枚举该子图中的所有s-t路径。
关于c++ - 如何记录从源顶点到目的顶点的所有最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16068811/