21
我一直在研究這三個，我在下面陳述他們的推論。有人能告訴我，我是否足夠精確地理解了它們？謝謝。我對Floyd-Warshall，Dijkstra和Bellman-Ford算法的區別是否正確？
Dijkstra算法只用於當你有一個單一來源，你想知道，從一個節點到另一個最小的路徑，但在案件未能像this
弗洛伊德 - 沃肖爾的算法時使用所有節點中的任何節點都可以成爲源節點，因此您希望最短距離能夠從任何源節點到達任何目標節點。這僅當有負向週期
（這是最重要的一個失敗。我的意思是，這是一個我至少肯定:)
3.Bellman，福特像迪傑斯特拉一樣，只有一個來源。這可以處理負重和它的工作方式與Floyd-Warshall相同，只有一個來源，對吧？
如果你需要看看，相應的算法（禮貌維基百科）：
貝爾曼 - 福特：
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]);
也許算法都寫在一本教科書的方式使它看起來像Dijkstra的僅用於單一來源，但這些算法可用於多個源和多個目標，幾乎不需要修改。對於Dijkstra而言，首先將源頂點放入距離爲0的優先級隊列中，如果需要多個源，只需將距離= 0的所有源都推送到該隊列中即可。或者，您可以將具有零重量邊的單個頂點添加到所有源頂點，然後將該頂點用作真實源。 – 2012-07-28 21:29:46
完全重複的：http://programmers.stackexchange.com/questions/158613/am-i-right-about-the-differences-between-floyd-warshall-dijkstras-and-bellman – 2012-07-28 21:57:20