私は最短経路アルゴリズムについて論文を書いています。と、ひとつわからないことが…
ダイクストラ アルゴリズムの視覚化を行いました。1) 正しいですか？それとも私は何か間違ったことをしていますか？2) Bellman-Ford アルゴリズムはどのように見えますか? 違いを探した限り、「Bellman-ford: 基本的な考え方は Dijkstra のものと非常に似ていますが、最短距離の隣接エッジを選択する代わりに、すべての隣接エッジを選択する」ことがわかりました。しかし、ダイクストラもすべての頂点とすべてのエッジをチェックしますよね?
dijkstra は、パスのコストが単調に増加していると仮定します。それに加えて、(プライオリティ キューを使用した) 順序付けされた検索により、最初にノードに到達したときに、最短パスを介して到達したことがわかります。
これは、負の重みには当てはまりません。負の重みで dijkstra を使用すると、後のパスが前のパスよりも優れていることがわかる場合があります (負の重みが後のステップでパスを改善したため)。
そのため、ベルマンフォードでは、ノードに到着したら、新しいパスが短いかどうかをテストします。対照的に、ダイクストラを使用すると、ノードをカリングできます
いくつかの (ほとんどの) 場合、dijkstra はすべての完全なパスを探索しません。たとえば、G が C のみにリンクされている場合、G を通るパスは、C を通るパスよりもコストが高くなります。bellman-ford は、G を経由して F に至るすべてのパスを引き続き考慮します (ダイクストラは、コストが高く、 C) を通過します。これを行わないと、負のループを見つけることを保証できません。
以下に例を示します。上記はパスAGEFを計算しません。E は、G から到着するまでに既に訪問済みとしてマークされています。
私も同じことを考えています
ダイクストラのアルゴリズムは、すべてのエッジの重みが負でない場合に、単一ソースの最短経路問題を解決します。これは貪欲なアルゴリズムであり、Prim のアルゴリズムに似ています。アルゴリズムはソース頂点 s から開始し、最終的に S から到達可能なすべての頂点にまたがるツリー T を成長させます。頂点は距離の順に T に追加されます。つまり、最初に S、次に S に最も近い頂点、次に最も近い頂点です。 、 等々。