加權有向非循環圖的最長路徑

我試圖將這個問題概念化，然後爲它編寫Java代碼。我知道這裏有一些討論，但我沒有看到很多答覆者，所以我想通過寫下我的想法來重申這個問題，我希望能夠從你們那裏獲得一些反饋。謝謝！加權有向非循環圖的最長路徑

我的想法：對於每一個葉節點查找根節點到它對於所有路徑的最長路徑找出最大路徑長度

然而，是不是這只是蠻力？有沒有更優雅的解決方案呢？

我聽說過使用Djikstra算法的負權重，但在某些地方它說這隻適用於特定的情況？我也看到了Bellman Ford算法的建議，但不是用來找到最短路徑的嗎？

謝謝！

2012-12-05 blazonix

我認爲你應該做的是計算根葉的所有最短路徑，然後取最長的計算路徑。一般來說，這將是一個難題，但幸運的是，您正在使用有向無環圖。實際上，由於這種限制，該算法會表現得很好。下面的代碼可以幫助你，它與yWorks開發，並從該site採取：

// To hold an edge list for every path. 
YList allShortestPaths = new YList(); 

// The actual number of proper shortest paths is unknown, so we start with a really great value for 'k'. 
YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph, edgeCostsDP, startNode, endNode, Integer.MAX_VALUE); 
if (pathCursor.ok()) 
{ 
    // The first path between the two nodes having least costs. 
    final EdgeList firstPath = (EdgeList)pathCursor.current(); 
    final double costsOfFirstPath = calculateCostsForPath(firstPath, edgeCostsDP); 

    allShortestPaths.add(firstPath); 
    pathCursor.next(); 

    // Look further. 
    while (pathCursor.ok()) 
    { 
    EdgeList currPath = (EdgeList)pathCursor.current(); 
    double currCosts = calculateCostsForPath(currPath, edgeCostsDP); 
    // If the current path is also a proper shortest path with costs equal to those 
    // of the first path, then add it to the list. 
    if (!(currCosts > costsOfFirstPath)) 
    { 
     allShortestPaths.add(currPath); 
     pathCursor.next(); 
    } 
    else 
     break; 
    } 
}

來源

2012-12-05 14:04:01

我們能做的拓撲排序，以獲得向無環圖（DAG）的頂點的排序。一旦我們有拓撲順序，我們就可以應用動態編程來獲得DAG中最長的路徑。

讓toposort後的頂點的索引是0,1,2，...，n-1個（總共n個圖中的頂點）

設F [I]是最長的值以頂點i結束的路徑。

然後，對於從i到所有的j，我們可以更新F [j]的爲F [j]的最大值=（F [j]時，F [I] 1）

我們可以通過初始化啓動每個出邊所有的F [I]的零然後循環從i = 1到n-1

最終答案將是最大{F [I]} 0 < = I < = N-1

來源

2013-05-28 08:24:15 nilmish

加權有向非循環圖的最長路徑

回答

相關問題