在有向圖中找到正長度的最短長度的循環

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