1

ダイクストラの最短経路アルゴリズムを認識しています。ただし、最短パスを見つける代わりに、貪欲なアルゴリズムを使用して最長パスを見つけるように変更するとします。以下のコードに対して何をしなければならないでしょうか。

これが私が使用しているものです：

最短パス バージョンで正しいノードを選択するための比較関数として:

 if (Cost(potential_node) > Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

ただし、裏返しにすると、これは機能しません。

 if (Cost(potential_node) < Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

少し混乱しています。フィードバックをいただければ幸いです

4

1 に答える 1

6

最長経路問題はNP-Hardであるため、既知の多項式解はありません。

dijkstra のアルゴリズムがノードを「閉じている」とマークするとき、それは意味するので、提案された変更は機能しません。ノードを閉じた場合、最長パスに対してそれを実行しようとすると、主張は正しくありません。ノードへのパスがなくなったことを意味するわけではありません。

これはまさに、各ステップでダイクストラのアルゴリズムで証明されていることを思い出してください (より多くの「緩和」は、より短いパスを見つけられません)。 the longest one - まだ探索されていない最長のパスが 1 つある可能性があります。

編集 - うまくいかない場合の反例 (私はひどい ascii アーティストであることを許してください)

        A
      /   \
     /     \
    1       2  
   /         \
  B-----5---> C
V = {A,B,C} ;  E = { (A,B,1), (A,C,2), (B,C,5) }

から始めてA、このアプローチは最初Cに「最長パス」を見つけて閉じます。これ以降、ダイクストラのアルゴリズムによると への変更はないため、 からへの最長パスの長さは 2 であり、パスはそれよりCも長いと結論付けることができます。ACA->B->C

于 2012-10-12T17:10:59.443 に答える