尋找鄰接表中最長的路徑

我有一個鄰接表，我已經創建了一個給定的圖與節點和加權邊緣。我試圖找出最好的方法是找出圖中最長的路徑。我有一種拓撲排序方法，我聽說它可能很有用，但我不確定如何實現它以找到最長的路徑。那麼有沒有一種方法可以使用拓撲排序來實現這一點，還是有更高效的方法？尋找鄰接表中最長的路徑

這裏是我出的形容詞列表的例子（括號中的數值是成本獲得該節點的箭頭(cost)to get to -> node後：

Node 0 (4)->1(9)->2 
Node 1 (10)->3 
Node 2 (8)->3 
Node 3 
Node 4 (3)->8(3)->7 
Node 5 (2)->8(4)->7(2)->0 
Node 6 (2)->7(1)->0 
Node 7 (5)->9(6)->1(4)->2 
Node 8 (6)->9(5)->1 
Node 9 (7)->3 
Node 10 (12)->4(11)->5(1)->6

來源

2013-04-30 bardockyo

布萊恩已經在上面回答了你的問題，但我想我可以更深入。

首先，正如他指出的那樣，如果沒有循環，這個問題就很容易解決。如果有周期，你會遇到無限長路徑的情況。在這種情況下，您可以將最長的路徑定義爲沒有重複節點的任何路徑。不幸的是，這個問題可以證明是NP-Hard。相反，我們將集中討論您實際需要解決的問題（因爲您提到了拓撲排序） - 有向非循環圖（DAG）中最長的路徑。我們還會假設我們有兩個節點s和t，這兩個節點是我們的開始和結束節點。除非您可以對圖形做出某些假設，否則問題有點醜陋。如果你理解了下面的文字，並且圖中的這些假設是正確的，那麼也許你可以刪除s和t限制（否則，你必須在圖的每對頂點上運行它！慢......）

該算法的第一步是拓撲排序頂點。直覺上這是有道理的。假設你從左到右排列它們（即，最左邊的節點將沒有進入的邊緣）。從s到t的最長路徑一般將從左側開始，結束於右側。這條路也不可能向左走。這將爲您提供連續的順序來生成最長的路徑 - 從左側開始並向右側移動。

下一步是按順序從左到右併爲每個節點定義最長的路徑。對於沒有傳入邊緣的節點，最長路徑到該節點爲0（根據定義，這是真的）。對於任何具有傳入邊緣的節點，遞歸定義最長路徑至該節點在所有傳入邊緣上爲最大+到達「傳入」鄰居的最長路徑（請注意，如果例如此數字可能爲負數，所有進入的邊緣都是負面的！）。直觀這是有道理的，但證據也簡單：

假設我們的算法聲稱，一些節點v最長路徑是d但實際最長路徑是一些d' > d。選擇「最少」這樣的節點v（我們使用按照拓撲排序定義的順序，換句話說，我們選擇算法失敗的「最左側」節點，這很重要，這樣我們就可以假設我們的算法已正確確定任何節點到v「左側」的最長路徑）。定義假想最長路徑的長度是d' = d_1 + e其中d_1是假想路徑向上的長度的節點v_prev與邊緣e到v（注意草率命名的邊沿e還具有重量e）。我們可以這樣定義它，因爲到v的任何路徑都必須通過其中一個具有邊緣將會到達v的鄰居（因爲您無法通過某條邊到達v）。然後d_1必須是到達v_prev的最長路徑（否則是矛盾的。有更長的路徑與我們選擇v作爲「最不」這樣的節點！）相矛盾！），並且我們的算法將根據需要選擇包含d_1 + e的路徑。

要生成實際路徑，您可以確定使用了哪條邊。假設您已經重建了路徑長度爲d的某個頂點v的路徑。然後遍歷所有進入的頂點並找到路徑長度最長的一個d' = d - e，其中e是進入v的邊的權重。當你通過算法時，你也可以跟蹤父母的節點。也就是說，當您找到v的最長路徑時，將其父項設置爲選擇相鄰節點的那個。你可以使用簡單的矛盾來說明爲什麼兩種方法產生最長的路徑。最後是一些僞代碼（對不起，它基本上是用C＃編寫的，在沒有自定義類的情況下在C中編寫代碼很麻煩，我也沒有編碼C）。

public List<Nodes> FindLongestPath(Graph graph, Node start, Node end) 
{ 
    var longestPathLengths = Dictionary<Node, int>; 

    var orderedNodes = graph.Nodes.TopologicallySort(); 
    // Remove any nodes that are topologically less than start. 
    // They cannot be in a path from start to end by definition 
    while (orderedNodes.Pop() != start); 
    // Push it back onto the top of the stack 
    orderedNodes.Push(start); 

    // Do algorithm until we process the end node 
    while (1) 
    { 
     var node = orderedNodes.Pop(); 
     if (node.IncomingEdges.Count() == 0) 
     { 
      longestPathLengths.Add(node, 0); 
     } 
     else 
     { 
      var longestPathLength = Int.Min; 
      foreach (var incomingEdge in node.IncomingEdges) 
      { 
       var currPathLength = longestPaths[incomingEdge.Parent] +    
            incomingEdge.Weight); 
       if (currPathlength > longestPathLength) 
       { 
        longestPath = currPathLength; 
       } 
      } 

      longestPathLengths.Add(node, longestPath); 
     } 

     if (node == end) 
     { 
      break; 
     } 
    } 

    // Reconstruct path. Go backwards until we hit start 
    var node = end; 
    var longestPath = new List<Node>(); 
    while (node != start) 
    { 
     foreach (var incomingEdge in node.IncomingEdges) 
     { 
      if (longestPathLengths[incomingEdge.Parent] == 
        longestPathLengths[node] - incomingEdge.Weight) 
      { 
       longestPath.Prepend(incomingEdge.Parent); 
       node = incomingEdge.Parent; 
       break; 
      } 
     } 
    } 

    return longestPath; 
}

請注意，此實現不是特別有效，但希望它很明顯！您可以通過許多小方法進行優化，這些方法在您考慮代碼/實現時應該很明顯。一般來說，如果你在內存中存儲更多的東西，它會運行得更快。你構建你的Graph的方式也很關鍵。例如，它看起來並不像你的節點有IncomingEdges屬性。但是如果沒有這些，找到每個節點的傳入邊是一種痛苦（並且不是高性能！）。在我看來，圖算法在概念上與字符串和數組算法有所不同，因爲實現非常重要！如果您閱讀圖表算法中的wiki條目，您會發現它們通常會根據不同的實現（具有不同的數據結構）提供三種或四種不同的運行時間。請記住，如果你關心速度

來源

2013-04-30 07:17:22 rliu

假設你的圖沒有周期，否則最長路徑變成了一個模糊的概念，你可以有一個拓撲排序，現在你可以走這個拓撲排序，並且每個節點通過查看它的所有前輩計算它與源節點的最長距離，並將連接到它們的邊的權重添加到它們距離，然後選擇能爲您提供此節點最長距離的前任。拓撲排序可確保您的所有前輩已經正確地距離它們的距離rmined。

如果除了最長路徑的長度外，還需要路徑本身。然後你從最長的節點開始，看看它的所有前輩，找到導致這個長度的節點。然後重複此過程直到找到圖的源節點。

來源

2013-04-30 00:22:44

尋找鄰接表中最長的路徑

回答

相關問題