algorithm - Dijkstra のアルゴリズムは貪欲または動的プログラミング アルゴリズムですか?

Question

この投稿では、ダイクストラスは貪欲なアルゴリズムとして説明されていますが、こことここでは動的計画法アルゴリズムとの関係があることが示されています。

じゃあどっち？

Answer 1

常に最も近い頂点をマークするので、貪欲です。以前に計算された値を使用して距離が更新されるため、動的です。

Answer 2

貪欲なアルゴリズムよりも動的計画法に近いと言えます。A から B までの最短距離を見つけるために、どの方向に進むかを段階的に決定するわけではありません。代わりに、A から行けるすべての場所を見つけて、最も近い場所までの距離をマークします。ただし、その場所にマークを付けたからといって、そこに行くわけではありません。これは、グラフのすべてのエッジが正であると仮定すると、距離を短くすることができなくなったことを意味するだけです。アルゴリズム自体には、どの方法で B をより速く配置できるかについての方向感覚がありません。最適な決定は貪欲に行われるのではなく、距離を短縮できる可能性のあるすべてのルートを使い果たすことによって行われます。したがって、これは動的計画法アルゴリズムです。唯一のバリエーションは、段階が事前にわからないことです。しかし、アルゴリズムの過程で動的に決定されます。必要に応じて、「動的」動的計画法アルゴリズムと呼んで、意思決定の所定の段階を経る他の動的計画法アルゴリズムと区別することができます。

Kruskal の最小スパニング ツリー アルゴリズムと比較すると、違いは明らかです。Kruskal のアルゴリズムでは、常にサイクルにつながらない最短のエッジを選択し、次に最短のエッジを選択します。最適な戦略は段階的に選択され、アルゴリズムでは 1 つの選択肢のみが実行されます。他の可能性は、数学的には最適ではないことが定理によって保証されていても、アルゴリズム的にはチェックまたは比較されません。私にとってクルスカルは貪欲ですが、ダイクストラは動的プログラミングです。