赋权有向无圈图的最长路

Question

我正在尝试将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写出我的想法来重申这个问题，我希望从你们那里获得一些反馈。谢谢!

我的想法是:对于每个叶节点，找出从根节点到它的最长路径。对于所有路径，找出最大路径长度

然而，这不是简单的蛮力吗？有没有更优雅的解决方案呢？

我听说使用带有负权重的Djikstra算法，但在某些地方它说这只在特定情况下有效？我也看到过关于Bellman Ford算法的建议，但这不是用来寻找最短路径的吗？

谢谢！！

Answer 1

我认为你应该做的是计算一个根到一个叶的所有最短路径，然后取计算出的最长路径。一般来说，这将是一个困难的问题，但幸运的是，您使用的是有向无环图。在实践中，由于这一限制，该算法将执行得非常好。下面的代码可能会对您有所帮助，它是用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;
  }
}

Answer 2

我们可以通过拓扑排序来得到有向无环图(DAG)的顶点排序。一旦我们有了拓扑排序，我们就可以应用动态编程来获得DAG中的最长路径。

设toposort后顶点的索引为0,1,2，...，n-1 (图中共有n个顶点)

设Fi是在顶点i结束的最长路径的值。

然后，对于从i到所有j的每个传出边，我们可以将Fj更新为Fj=max(Fj，Fi+1)

我们可以从初始化所有Fi为零开始，然后从i=1循环到n-1

最终答案是max{Fi} 0<=i<=n-1