Dijkstra vs BellFordアルゴリズム

Question

Dijkstrasアルゴリズムを使用するか、BellFordアルゴリズムを使用する必要があるのか​​を、あるソースからグラフ内の他のすべての頂点まで最短経路を見つける必要がある場合

Answer 1

Dijkstraが適切に実装されているのはBellman-Fordよりも高速なので、グラフに負のウェイトエッジがない限りDijkstraを使用してください。この場合、Dijkstraは間違っている可能性がありますが、Bellman-Fordは正しい答えを返します。

グラフのウェイトが負の場合、最短経路は明確に定義されていません。ベルマンフォードは、与えられたグラフが負の重みサイクルを有するかどうかをチェックできるように修正することができる。