弗洛伊德-沃舍尔算法、迪杰斯特拉算法和贝尔曼-福德算法之间的区别,我的理解正确吗?

22

我已经学习了这三个算法,并在下面陈述了我的推论。请问是否有人能告诉我我是否理解得足够准确?谢谢。

  1. Dijkstra算法仅在您有一个单一源并且想要知道从一个节点到另一个节点的最短路径时使用,但在像这样的情况下会失败。

  2. Floyd-Warshall算法用于任何节点都可以是源头的情况,因此您希望找到从任何源节点到达任何目标节点的最短距离。只有当存在负循环时,该算法才会失败。

(这是最重要的一个。我的意思是,我对这个问题最不确定:)

3.Bellman-Ford算法与Dijkstra类似,用于仅有一个源头的情况。它可以处理负权重,除了只有一个源头之外,其工作方式与Floyd-Warshall相同,对吗?

如果您需要查看相应的算法,请参考(由维基百科提供):

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;

Floyd-Warshall算法:

 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。或者,您可以向所有源顶点添加具有零权重边缘的单个顶点,然后将该顶点用作实际源。 - Running Wild
3
这是文本翻译:与 http://programmers.stackexchange.com/questions/158613/am-i-right-about-the-differences-between-floyd-warshall-dijkstras-and-bellman 完全相同。 - Håvard Geithus
2个回答

21
您对前两个问题的回答是正确的,Floyd-Warshall的目标也确实是找到所有节点对之间的最短路径,但是关于Bellman-Ford和Floyd-Warshall之间的关系,您并不正确:这两种算法都使用动态规划来寻找最短路径,但FW并不等同于从每个起始节点运行BF到每个其他节点。
在BF中,问题是:源到目标的最短路径最多可以使用k步,运行时间为O(E
在FW中,问题是:对于所有节点i、j、k,i到j的最短路径通过k。这导致O(V^3)的运行时间-对于每个起始节点比BF更好(在密集图中长达| V |倍)。
关于负环/权重的另一个说明:Dijkstra可能仅仅会失败而不能给出正确结果。BF和FW不会失败-它们将正确地说明没有最小权重路径,因为负权重是无界的。

1
BF和FW指定的运行时间是正确的,但它们的描述是相反的。在FW的每个阶段中,1到k之间的所有顶点都被视为“通过”节点。而在BF中,k表示从i到j所需的边数k,而不是相反的情况。 - Farhad Alizadeh Noori

9

单源最短路径:

Dijkstra 算法 - 不允许负权重 - 时间复杂度为 O(E+Vlg(V))

Bellman Ford 算法 - 允许负权重。但如果存在负环,Bellman Ford 将检测到该负环 - 时间复杂度为 O(VE)

有向无环图 - 顾名思义,仅适用于 DAG - 时间复杂度为 O(V+E)

所有点对最短路径:

Dijkstra 算法 - 不允许负权重 - 时间复杂度为 O(VE + V^2lg(V))

Bellman Ford 算法 - 时间复杂度为 O(V^2E)

矩阵链乘法 - 复杂度与 Bellman Ford 算法相同

Floyd Warshall 算法 - 使用动态规划方法 - 时间复杂度为 O(V^3)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接