12 
   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

さて、これがグラフです。私の送信元ノード1と宛先ノードは5

私の質問はです。

両方のアルゴリズムで同じ出力が得られるかどうか? つまり、両方が返され1->2->4->5ますか? (ただし、ダイクストラでは負の重みは許可されません)

助けてくれてありがとう。

4

3 に答える 3

26

Bellman-Ford アルゴリズムは、単一ソースの最短経路アルゴリズムであり、負のエッジの重みを考慮し、グラフ内の負のサイクルを検出できます。

ダイクストラ アルゴリズムも、単一ソースの最短パス アルゴリズムの 1 つです。ただし、すべてのエッジの重みは負でない必要があります。

あなたの場合、総コストに関する限り、グラフのエッジには負でない重みがあるため、違いはありません。Theta((|E|+|V|)log|V|)ただし、 Bellman-Ford アルゴリズムは複雑であるのに対し、バイナリ ヒープを使用した一般的な実装には時間の複雑さがあるため、ダイクストラのアルゴリズムが通常使用されますO(|V||E|)。

最小コストのパスが複数ある場合、返される実際のパスは実装に依存します (同じアルゴリズムであっても)。

于 2013-04-29T07:24:51.477 に答える