Dijkstraのアルゴリズムとサイクル

「DijkstraのアルゴリズムはDirected Acyclic Graphsでのみ動作する」と書かれています。Dijkstraのアルゴリズムとサイクル

このアルゴリズムは、負のサイクルがない限り、サイクルのグラフでも機能します。あれは正しいですか？

編集1：本「Grokking Algorithms」 - Aditya Bhargava。第7章Page 122

出典

2017-04-13 sam

は...あなたの引用します偽です。 –

私は聞くかもしれないが、どの本？あなたがそのような見積もりを見つけるためにどこで詳細を提供できるかは素晴らしいでしょう。 – maxik

実際には、すべてのエッジ重みが負でない限り動作します。これは、「負のサイクルなし」としてのより強い条件である。一方、負の重みを持つDAGでは動作しません。だから、あなたが正しく引用されていれば、本の声明は2つの理由から間違っています。

Btw。負のサイクルがある場合は、無限回繰り返す可能性があるため、最短の経路がなくなり、コストは下がります。

出典

2017-04-13 14:32:05 Henry

ありがとうございます@Henry – sam

私はGrokkingアルゴリズムの著者です。このエラーで申し訳ありません.Dijkstraのアルゴリズムは、正のウェイトサイクルである限り、サイクルでグラフ上でを処理しますか？このエラーを反映するようにerrata pageを更新しました。ダイクストラは負の重みサイクルでは動作しません。また、ここに理由を説明する画像です：あなたはそれを巡回グラフのために働くのコースの「最短経路アルゴリズム」を参照している場合は

dijkstra's algorithm with a negative weight cycle

出典

2017-05-06 16:39:24

Dijkstraのアルゴリズムとサイクル

答えて

関連する問題