Dijkstra法とWarshall-Floyd法について

[hum-king]

それぞれの利点がいまいち分かりません。。。それぞれの利点・欠点を述べよ。という課題が出たのですがよく分かりません＾＾； 今の時点で自分が考えたことを書きます。間違えているかもしれませんが・・・


◎利点

・実装が簡単(ワーシャル・フロイド)

・グラフが密な場合はダイクストラよりワーシャル・フロイドの方が早い。
→でもWebなどを見ていると実行時間はダイクストラと同じと書いてありました。実際に実行してみるとワーシャル・フロイドの方が早かったです。ここがイマイチ理解しがたいところの一つです。

・逆にグラフが疎な場合はダイクストラの方が早いらしいです。
・負の閉路があっても用いれる(ワーシャル・フロイド)


●欠点

・グラフが密な場合は計算が終わらない。(ダイクストラ)
・負の閉路がある場合は使えない。(ダイクストラ)


少ないですが、今はこんなところです＾＾；どなたかお知恵貸して下さる方がいらっしゃったらよろしくお願いします。

[parapara]

たった一つの事で、知ってるかもしれませんが、
ダイクストラは改良する事で、閉路の判定が出来た気がする。