0

私はこの問題を概念化してから、そのためのJavaコードを作成しようとしています。ここでいくつかの議論があったことは知っていますが、回答者があまりいないので、私の考えを書き留めて質問を繰り返したいと思います。皆さんからのフィードバックを期待しています。ありがとう！

私の考え：各リーフノードについてルートノードからそのノードまでの最長パスを見つけるすべてのパスについて最大パス長を見つける

しかし、これは単なるブルートフォースではありませんか？これに対するよりエレガントな解決策はありますか？

負の重みでダイクストラのアルゴリズムを使用していると聞きましたが、一部の場所では、これは特定のケースでのみ機能すると言われていますか？ベルマンフォードアルゴリズムの提案も見ましたが、それは最短経路を見つけるために使用されていませんか？

ありがとう！！

4

2 に答える 2

3

あなたがすべきことは、ルートからリーフへのすべての最短経路を計算し、計算された経路のうち最長のものを取ることだと思います。一般に、これは難しい問題ですが、幸いなことに、有向非巡回グラフを使用しています。実際には、この制限により、アルゴリズムは非常にうまく機能します。次のコードが役に立つかもしれません。これは 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;
  }
}
于 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 に答える