寻找包含两个节点的最短循环

Question

令 G=(E,V) 为具有非负边成本的有向图。让 s 成为一个顶点。我需要找到一种算法，为每个顶点 v 找到包含 s 和 v 的最短循环。该循环可能多次包含相同的边。

显而易见的解决方案是从 s 运行 Dijkstra，以找到从 s 到每个 v 的最短路径。然后，从每个 v 再次运行 Dijkstra，以找到从 v 到 s 的最短路径。最短周期是两者的结合。

这可行，但需要 O(|V||E| + |V|^2*log|V|)。有更好的解决方案吗？

Answer 1

对于有向图，您可以使用Floyd-Warshall 算法来查找所有两对之间的最短路径。

或者更有效的解决方案可能是在反转图上运行 Dijsktra （G'=(V,E')这样对于每个(v,u)in E，(u,v)is in E'），并将两个解决方案连接起来（当然一个是相反的）。这基本上是运行 Dijkstra 两次。