问求包含两个节点的最短循环
EN

Stack Overflow用户

提问于 2013-05-03 11:50:07

回答 1查看 941关注 0票数 2

设G=(E，V)是具有非负边代价的有向图.让我们做一个顶点。我需要找到一个算法，为找到每个顶点v，包含s和v的最短循环可能包含几次相同的边。

最明显的解决办法是从s中运行Dijkstra，以求从s到每个v的最短路径，然后从每个v再运行Dijkstra，以求从v到s的最短路径，最短的循环是两者的结合。

这是可行的，但将使用O(\x，V，x，E，O，E，E，O，E，E，O)，+V，*，这是可行的，但却需要使用O(x=0)。有没有更好的解决办法？

回答已采纳

发布于 2013-05-03 12:11:42

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

或者更有效的解决方案可以是在反向图上运行Dijsktra (G'=(V,E')使E中的每个(v,u)在E'中，(u,v)在E'中)，并连接这两个解决方案(当然，一个相反)。这基本上是运行Dijkstra两次.

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/16358259

复制

相似问题

问求包含两个节点的最短循环EN