我是对弗洛伊德 - 战争,迪尔赫斯特拉和贝尔曼福特算法之间的差异吗?
-
13-12-2019 - |
题
我一直在学习这三个,我正在向下陈述我的推论。有人可以告诉我我是否已经准确理解或不够理解?谢谢。
-
dijkstra的算法仅在您拥有一个源时使用,并且您希望从一个节点到另一个节点的最小路径,但在这个
-
弗洛伊德 - 弗洛伊德 - 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] );
.解决方案
您对前两个问题是正确的,以及弗洛伊德 - 战争的目标(找到所有对之间的最短路径),但不是关于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不会失败 - 它们将正确地说明没有最小权重路径,因为负重无限。
其他提示
单源最短路径:
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)