0

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

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

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

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

谢谢！！

4

2 回答 2

3

I think what you should do is to calculate all shortest paths of a root to a leaf and then take the longest of the calculated paths. In general this would be a hard problem but fortunately you are using a directed acyclic graph. In practice the algorithm will perform very well due to this restriction. The following code may help you, it was developed with yWorks and taken from this 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-05T14:04:01.350 回答
2

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

令toposort后顶点的索引为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<=i<=n-1

于 2013-05-28T08:24:15.110 回答