4

私はダイクストラのアルゴリズムを理解し、実装するために一日中戦ってきましたが、重要な結果はありませんでした。私は都市とその距離のマトリックスを持っています。私がやりたいのは、出発地と目的地を指定して、都市間の最短経路を見つけることです。

例：

     __0__ __1__ __2__ 
 0  |  0  | 34  |  0  |
    |-----|-----|-----|
 1  | 34  |  0  | 23  |
    |-----|-----|-----|
 2  |  0  | 23  |  0  |
     ----- ----- -----

これを解決する他の方法があるかどうか疑問に思い始めました。プリムのアルゴリズムを起点から適用し、作成されたツリー全体をループして、終点が見つかるとどうなりますか？

4

1 に答える 1

5

Prim のアルゴリズムを適用して、結果のツリーをたどることができますが、答えが間違っている可能性があります。各辺の重みが同じグラフがあるとします。Prim のアルゴリズムは、ツリーに追加できるエッジのセットから最小の重みのエッジを選択するだけです。2 つのノード間の最短パスにつながるエッジを選択しない可能性があります。推定：

     __0__ __1__ __2__ 
 0  |  0  |  1  |  1  |
    |-----|-----|-----|
 1  |  1  |  0  |  1  |
    |-----|-----|-----|
 2  |  1  |  1  |  0  |
     ----- ----- -----

ノード 0 から始めて、Prim を介して、エッジ 0-1 と 0-2 を選択してツリーを作成できます。または、エッジ 0-1 と 1-2 を選択してツリーを作成することもできます。最初のエッジ セットの下では、0 から 2 までの最小長のパスを見つけることができましたが、2 番目のエッジ セットの下では最小パスを見つけることができませんでした。Prim アルゴリズムではどのエッジが追加されるかをアプリオリに判断できないため、それを使用して最短経路を見つけることはできません。

Bellman-Fordアルゴリズムを検討することもできますが、負のエッジの重みを扱っていない限り、Dijkstra のアルゴリズムが望ましいと思います。

于 2011-03-20T17:42:26.977 に答える