在有向图中找到正长度的最短长度的循环

Question

我在一次采访中被问到了这个问题，但我无法想出任何像样的解决方案。所以，我告诉他们寻找所有循环的幼稚方法，然后选择最短的循环。

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

Answer 1

您可以轻松地修改Floyd-Warshall algorithm见Algorithms in C++ Part5 - Robert Sedgwick。 （如果你根本不熟悉图论，我建议检查一下，例如获得Introduction to Algorithms的副本）。

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

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

另外，您还可以使用Dijkstra's algorithm来查找经过任何给定节点的最短周期。如果你为每个节点运行这个修改后的Dijkstra，你将得到与Floyd-Warshall相同的结果。而且由于每个Dijkstra都是O(n^2)，你会得到相同的整体复杂度。

Answer 2

• 执行DFS
• DFS期间保持边缘类型的轨道
• 型边缘的位置是Tree Edge，Back Edge，Down Edge和Parent Edge
• 跟踪，当你得到一个Back Edge并有另一个柜台为了获得长度。

更多细节

Answer 3

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

Answer 4

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

Answer 5

我们也可以使用分支定界算法旅行商问题，你的问题与TSP相匹配。 http://lcm.csa.iisc.ernet.in/dsa/node187.html