我是对弗洛伊德 - 战争，迪尔赫斯特拉和贝尔曼福特算法之间的差异吗？

Question

我一直在学习这三个，我正在向下陈述我的推论。有人可以告诉我我是否已经准确理解或不够理解？谢谢。

1. dijkstra的算法仅在您拥有一个源时使用，并且您希望从一个节点到另一个节点的最小路径，但在这个

2. 弗洛伊德 - 弗洛伊德 - Warshall的算法是使用所有节点可以是源的，因此您希望从任何源节点到达任何目标节点的最短距离。当存在负循环时，这仅失败

（这是最重要的一个。我的意思是，这是我最不确定的:)

3.bellman-ford像Dijkstra一样使用，当时只有一个来源。这可以处理负重和它的工作与弗洛伊德战争的工作相同，除了一个来源，右边？

如果您需要看，相应的算法是（礼貌维基百科）：

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] );

.

Answer 1

您对前两个问题是正确的，以及弗洛伊德 - 战争的目标（找到所有对之间的最短路径），但不是关于Bellman-Ford和Floyd-Warshall之间的关系：这两种算法都使用动态编程找到最短路径，但FW与从每个起始节点运行BF到每个其他节点的FW不一样。

在bf中，问题是：最多使用大多数k步骤的源到目标的最短路径是什么，运行时间是o（e v）。如果我们要将其运行到彼此节点，则运行时间将是O（e v ^ 2）。

在fw中，问题是：对于所有节点i，j，k，我到j到k的最短路径是什么？这导致O（v ^ 3）运行时间 - 对于每个起始节点的BF更好（通过致密的图形为v | for to | for for dent |。

一个关于负周期/权重的备注：Dijkstra可能只需提供正确的结果。 BF和FW不会失败 - 它们将正确地说明没有最小权重路径，因为负重无限。

Answer 2

单源最短路径：

dijkstra算法 - 不允许负重 - o（e + vlg（v））

Bellman Ford算法 - 允许负重。但如果存在负周期，则Bellman Ford将检测-ve Cycle - O（VE）

定向无循环图 - AS名称表明它仅适用于DAG - O（v + e）

所有对最短路径：

Dijkstra算法 - 不允许负重 - O（VE + V ^ 2LG（V））

Bellman Ford算法 - O（v ^ 2e）

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

Floyd Warshall算法 - 使用动态编程方法 - 复杂性是O（v ^ 3）