フロイドウォーシャル、Dijkstra、Bellman-Fordアルゴリズムの違いについて私は正しいですか？
https://stackoverflow.com//questions/11704643
-
13-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は3人を勉強しています、そして私はそれらから私の推論を下に述べています。私が正確にそれらを十分に理解しているかどうかを誰かが私に言うことができますか？ありがとうございました。
-
Dijkstraのアルゴリズムは、単一のソースがある場合にのみ使用され、1つのノードから別のノードへの最小パスを知りたいが、この
-
Floyd-Warshallのアルゴリズムは、すべてのノードのいずれかがソースになる場合が使用されるため、最短距離が任意のソースノードから任意の宛先ノードに到達します。これは負のサイクルがあるときにのみ失敗する
（これは最も重要なものです。つまり、これは私が最も確実なもの最も確実なものです:)
3.Bellman-fordは、ソースが1つしかない場合、Dijkstraのように使用されます。これは否定的な重みを扱うことができ、その作業は1つの情報源を除いてフロイドウォーシャルの右側を除いて同じですね。
あなたが外観を持つ必要があるなら、対応するアルゴリズムは（礼儀ウィキペディア）：
Bellman-Ford：
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges: // uv is the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
Dijkstra：
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 // from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 if dist[u] = infinity:
14 break ; // all remaining vertices are
15 // inaccessible from source
16
17 remove u from Q ;
18 for each neighbor v of u: // where v has not yet been
19 removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 return dist;
フロイドウォーシャル：
1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
2 (infinity if there is none).
3 Also assume that n is the number of vertices and edgeCost(i,i) = 0
4 */
5
6 int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8 from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to
9 edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13 for k := 1 to n
14 for i := 1 to n
15 for j := 1 to n
16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
解決
最初の2つの質問について、そしてフロイド・ウォーシャルの目標について正しい（すべてのペア間の最短経路を見つける）が、Bellman-FordとFloyd-Warshallの間の関係ではありません：両方のアルゴリズムは動的プログラミングを使用します最短パスを見つけますが、FWは各開始ノードから他のすべてのノードへのBFの実行と同じではありません。
BFでは、質問は次のとおりです。ほとんどのKステップを使用して、ソースからターゲットへの最短経路とは何ですか、走行時間はO（e em> v）です。他のノードに実行する場合は、実行時間はO（E V ^ 2）になります。
FWでは、問題は次のとおりです。すべてのノードi、j、kに対して、iからjへの最短経路とは何ですか。これにより、o（v ^ 3）実行時間 - 始動ノードごとにBFよりも優れています（V |密度グラフについて）。
負のサイクル/重みに関するもう1つの注意：Dijkstraは単に正しい結果を与えることができないかもしれません。 BFとFWは失敗することはありません - 負の重みが無制限のため、最小の重みパスがないと正しく述べています。
他のヒント
シングルソース最短パス：
Dijkstraアルゴリズム - 負の重みなし許可点 - O（E + VLG（V））
ベルマンフォードアルゴリズム - 負の重みが許可されています。しかし、負のサイクルが存在する場合Bellman Fordは-veサイクルを検出します - O（VE）
有向性非巡回グラフ - 名前がDAG - O（V + E）
のみに動作することを示唆しているようにすべてのペア最短パス：
Dijkstraアルゴリズム - 負の重みが許可されていない - O（VE + V ^ 2LG（V））
ベルマンフォードアルゴリズム - O（V ^ 2e）
マトリックスチェーン乗算法 - Bellmanフォードアルゴリズムと同じであるComplexity
Floyd Warshallアルゴリズム - 動的プログラミング方法 - 複雑さはO（V ^ 3）
です。
