如何记录到一个目标顶点从源顶点的所有最短路径 [英] How to record all the shortest paths from a source vertex to a destination vertex

问题描述

我目前使用加速图形库的Dijkstra算法 http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html 以计算一对顶点之间最短距离的路径。到目前为止，我只能获取存储在predecessor映射将一个最短路径。

I'm currently using Boost graph library's dijkstra algorithm http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html to compute shortest distance path between a pair of vertices. So far, I can only obtain one shortest path stored in the predecessor map.

所以我的问题是：是否有可能让函数返回一个对顶点之间所有可能的最短路径

So my question is: is it possible to let the function return all possible shortest paths between a pair of vertices?

推荐答案

没有，你需要建立一个自己。一种方法是计算从源点s（在G）和向信宿顶点吨的距离（即，从T中的转置图形距离）使用两次调用迪杰斯特拉。然后，提取恰好含有这些节点Ü使得距离的子图（S，U）+距离（U，T）=距离（S，T）和那些弧UV使得距离（S，U）+长度（U，V ）+距离（V，T）=距离（S，T）和递归枚举所有的ST路径在这个子。

No, you need to build that yourself. One way is to compute distances from the source vertex s (in G) and to the sink vertex t (i.e., distances from t in the transpose graph) using two calls to Dijkstra. Then, extract a subgraph containing exactly those nodes u such that distance(s, u) + distance(u, t) = distance(s, t) and those arcs uv such that distance(s, u) + length(u, v) + distance(v, t) = distance(s, t) and recursively enumerate all s-t paths in this subgraph.

这篇关于如何记录到一个目标顶点从源顶点的所有最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！