嗨，我正在努力解决这个问题 . 它是以下内容：
设计算法以在加权有向图G =（V，E）中找到最低权重周期（即图中所有周期，边缘权重之和最小的周期） . 简要说明运行时和空间复杂性 . 假设所有边都是非负的 . 它应该在O（| V || E | log | V |）时间运行 . 提示：使用Dijkstra算法的多个调用 .
我见过使用Floyd-Warshall的解决方案，但我想知道我们如何使用Dijkstra's以及如何在给定的时间限制内完成此操作 .
我有几点困惑：
-
首先，我们如何知道图表中有多少个周期以及如何检查这些周期？
-
另外，为什么它是| E || V | log | V |？根据我的理解，你应该遍历所有的顶点，因此使它成为| V | log | V | .
这是我个人的学习，所以如果有人有他们可以使用的例子，那将对我有很大的帮助！我并不是在寻找伪代码 - 只是一种通用算法来理解如何使用从一个节点到所有节点的最短路径来帮助我们解决这个问题 . 谢谢！
1 回答
从每个顶点调用Dijkstra算法，找到自己的最短路径（如果存在） . 从任何顶点到自身的最短路径是最小的循环 . Dijkstra的算法取O（| E | log | V |），因此总时间为O（| V || E | log | V |） .
注意，这个时间可能比Floyd-Warshall差，因为图中可能有O（| V | ^ 2）个边 .