加权有向非循环图的最长路径

我试图将这个问题概念化，然后为它编写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

加权有向非循环图的最长路径

回答

相关问题