令 G=(E,V) 为具有非负边成本的有向图。让 s 成为一个顶点。我需要找到一种算法，为每个顶点 v 找到包含 s 和 v 的最短循环。该循环可能多次包含相同的边。
显而易见的解决方案是从 s 运行 Dijkstra，以找到从 s 到每个 v 的最短路径。然后，从每个 v 再次运行 Dijkstra，以找到从 v 到 s 的最短路径。最短周期是两者的结合。
这可行，但需要 O(|V||E| + |V|^2*log|V|)。有更好的解决办法吗？
最佳答案
对于有向图，您可以使用Floyd-Warshall Algorithm找到所有两对之间的最短路径。
或者更有效的解决方案可能是在反转图上运行 Dijsktra (G'=(V,E') 这样对于每个 (v ,u) 在 E 中，(u,v) 在 E' 中)，并将两个解(一个在当然是相反的)。 这基本上是运行 Dijkstra 两次。
关于algorithm - 寻找包含两个节点的最短循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16358259/