加权有向无环图的最长路径

Question

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

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

然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？

我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关于贝尔曼-福特算法的建议，但这不是用来找到最短路径的吗？

谢谢

Answer 1

我们可以对有向无环图（DAG）的顶点进行拓扑排序。一旦我们有了拓扑排序，我们就可以应用动态规划来获得DAG中最长的路径。

让拓扑排序后顶点的索引为 0，1，2,....,n-1（图中总共 n 个顶点）

设 F[i] 是结束于顶点 i 的最长路径的值。

然后，对于从 i 到所有 j 的每个传出边，我们可以将 F[j] 更新为 F[j]=max（F[j]，F[i] 1）

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

最终答案是max{F[i]} 0

Answer 2

我认为你应该做的是计算一个根到一片叶子的所有最短路径，然后取计算出的最长路径。一般来说，这将是一个困难的问题，但幸运的是，你使用的是有向无环图。实际上，由于这种限制，该算法将执行得非常好。下面的代码可能对你有所帮助，它是用yWorks开发的，取自这个网站:

// 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;
  }
}