22

我在一次采访中被问到这个问题，但我想不出任何合适的解决方案。所以，我告诉他们找到所有周期然后选择长度最短的周期的幼稚方法。

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

4

5 回答 5

35

您可以轻松修改Floyd-Warshall 算法。（如果您根本不熟悉图论，我建议您检查一下，例如获取一份算法简介）。

传统上，您从path[i][i] = 0每个i. 但您可以改为从path[i][i] = INFINITY. 它不会影响算法本身，因为无论如何这些零都没有用于计算（因为路径path[i][j]永远不会改变k == ior k == j）。

最后，path[i][i]是最短循环经过的长度i。因此，您需要查找min(path[i][i])所有i. 如果你想要循环本身（不仅仅是它的长度），你可以像通常使用普通路径一样完成它：通过k在算法执行期间记忆。

此外，您还可以使用Dijkstra 算法找到通过任何给定节点的最短循环。如果您为每个节点运行此修改后的 Dijkstra，您将获得与 Floyd-Warshall 相同的结果。由于每个 Dijkstra 都是O(n^2)，因此您将获得相同的O(n^3)整体复杂性。

于 2010-10-12T07:48:39.943 回答
6

伪代码是对 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)

于 2015-11-02T03:39:42.913 回答
0
  • 执行 DFS
  • 在 DFS 期间，跟踪边缘的类型
  • 边的类型是Tree Edge、Back Edge和Down EdgeParent Edge
  • Back Edge当你得到一个并有另一个计数器来获取长度时跟踪。

查看Algorithms in C++ Part5 - Robert Sedgwick更多详情

于 2010-10-12T05:34:50.210 回答
0

您需要做的是为每个节点分配另一个权重，该权重始终为 1。现在使用这些权重运行从一个节点到同一节点的任何最短路径算法。但是在考虑中间路径时，您将不得不忽略实际权重为负的路径。

于 2010-10-12T10:03:02.520 回答
0

下面是对 Floyd - Warshell 算法的简单修改。

V = 4
INF = 999999



def 最小周期长度（图）：
    dist = [[0]*V for i in range(V)]
    对于范围内的 i (V)：
            对于范围（V）中的j：
                dist[i][j] = 图[i][j];
    对于范围（V）中的k：
        对于范围内的 i (V)：
            对于范围（V）中的j：
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
    长度 = INF
    对于范围内的 i (V)：
        对于范围（V）中的j：
            长度 = min(长度,dist[i][j])
    返回长度


graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length
于 2018-08-10T17:37:28.037 回答