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

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)是 in E'），并连接两个解决方案（当然是一个相反的解决方案）。这基本上是运行 Dijkstra 两次。