在具有正权重的有向图中找出最短长度的循环

Question

我在接受采访时被问到这个问题,但我无法提出任何合适的解决方案.所以,我告诉他们找到所有周期然后选择长度最短的周期的天真方法.

我很想知道什么是这个问题的有效解决方案.

Answer 1

您可以轻松修改Floyd-Warshall算法.(如果您根本不熟悉图论,我建议您查看它,例如获取算法简介的副本).

传统上,你从path[i][i] = 0每个开始i.但你可以从而开始path[i][i] = INFINITY.它不会影响算法本身,因为无论如何这些零都没有用在计算中(因为路径path[i][j]永远不会改变k == i或k == j).

最后,path[i][i]是最短周期的长度i.因此,您需要找到min(path[i][i])所有人i.如果你想要自行循环(不仅仅是它的长度),你可以像通常使用普通路径一样进行循环:通过k在算法执行期间记忆.

此外,您还可以使用Dijkstra算法查找通过任何给定节点的最短周期.如果你为每个节点运行这个修改过的Dijkstra,你将获得与Floyd-Warshall相同的结果.而且由于每个Dijkstra都是O(n^2),你将获得相同的O(n^3)整体复杂性.

Answer 2

伪代码是Dijkstra算法的简单修改.

for all u in V:
   for all v in V:
      path[u][v] = infinity

for all s in V:
   path[s][s] = 0
   H = makequeue (V) .. using pathvalues in path[s] array as keys
   while H is not empty:
      u = deletemin(H)
      for all edges (u,v) in E:
         if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
            path[s][v] = path[s][u] + l(u,v)
         decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
   if path[v][v] < lengthMinCycle & path[v][v] != 0 :
      lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
   print(“The graph is acyclic.”)

else:
   print(“Length of minimum cycle is ”, lengthMinCycle)

时间复杂度:O(| V | ^ 3)