プリムのアルゴリズムとダイクストラ法の違いについて

Question

前提・実現したいこと

プリムのアルゴリズムとダイクストラ法の違いが分からずに困っています。

プリム法は最小全域木、ダイクストラ法は２点間の最短経路を求めるアルゴリズムだという事は理解しているのですが、結局最小全域木で２点間を辿れば最短経路になる様に思えるので、ダイクストラ法の必要性がよく分からずにいます。

どなたか詳しくご説明していただけませんでしょうか。

Answer 1

最大の違いは、ダイクストラ法には「スタート地点・ゴール地点」という概念があることです。プリム法では最小スパニング木ができますが、ダイクストラ法でできるのは、スタート地点を根とした最短経路スパニング木です。
そのため、外部の点を木に入れるときの計算方法が異なります。プリム法では、新しい辺を加えるときに、木の内部と外部を結ぶ辺の重みしか考慮しません。これに対してダイクストラ法では、木の内部と外部を結ぶ辺の重みに加え、その辺のうち木の内部にある方の頂点とスタート地点との距離も考慮します。

わかりやすい例として、正三角形ABCとその重心Dを考えてみてください。AからDの4点をつなぐ最小スパニング木はD-A, D-B, D-Cの3本の直線で構成されるものになりますが、AからBへの最短経路は明らかにA-Bです。
点Aを根とした最短経路スパニング木は、A-B, A-C, A-Dの3本の直線で構成されるものになります。

Comments

[maskey]

ご丁寧な解説をありがとうございます！
なるほど、最小全域木上の経路が必ずしも２点間の最短経路とはならないのですね。正三角形の具体例のおかげで、スムーズに理解出来ました。
ご回答頂きありがとうございました。