单源最短路径算法(假设图中存在负循环)
在阅读这个例子之前,需要对边缘松弛有一个简短的想法。你可以从这里学到它
Bellman-Ford 算法计算从单个源顶点到加权有向图中所有其他顶点的最短路径。即使它比 Dijkstra 算法慢,但它适用于边缘权重为负且在图中也发现负权重周期的情况。Dijkstra 算法的问题是,如果存在负循环,则会一次又一次地继续循环并继续减小两个顶点之间的距离。
该算法的思想是以一些随机顺序逐个遍历该图的所有边缘。它可以是任何随机顺序。但是你必须确保,如果 uv (其中 u 和 v 是图中的两个顶点)是你的一个命令,那么必须有一个从 u 到 v 的边。通常它直接取自给定输入的顺序。同样,任何随机顺序都可以。
选择顺序后,我们将根据放松公式放松边缘。对于从 u 到 v 的给定边缘 uv ,松弛公式为: **** ****
if distance[u] + cost[u][v] < d[v]
d[v] = d[u] + cost[u][v]
也就是说,如果从源到任何顶点的距离 u + 边缘 uv 的权重小于从源到另一个顶点 v 的距离,我们更新从源到 v 的距离。我们需要放松边缘最多 (V-1) 次,其中 V 是图中边的数量。为什么 (V-1) 你问?我们将在另一个例子中解释它。此外,我们将跟踪任何顶点的父顶点,也就是当我们放松边缘时,我们将设置:
parent[v] = u
这意味着我们找到了另一条通过 u 到达 v 的较短路径。稍后我们将需要它来打印从源到目标顶点的最短路径。 **** ****
我们来看一个例子。我们有一个图表:
我们选择 1 作为源顶点。我们想要找出从源到所有其他顶点的最短路径。
首先, d [1] = 0,因为它是源。休息是无限的,因为我们还不知道他们的距离。
我们将按顺序放松边缘:
+--------+--------+--------+--------+--------+--------+--------+
| `Serial` | 1 | 2 | 3 | 4 | 5 | 6 |
+--------+--------+--------+--------+--------+--------+--------+
| Edge | 4->5 | 3->4 | 1->3 | 1->4 | 4->6 | 2->3 |
+--------+--------+--------+--------+--------+--------+--------+
你可以采取任何你想要的顺序。如果我们放松一下边缘,我们得到什么?我们得到从源到最多使用 1 个边的路径的所有其他顶点的距离。现在让我们放松边缘并更新 d [] 的值。我们得到:
- d [4] + 成本[4] [5] = 无穷大 + 7 = 无穷大。我们无法更新这个。
- d [2] + 成本[3] [4] = 无穷大。我们无法更新这个。
- d [1] + 成本[1] [2] = 0 + 2 = 2 < d [2] 。所以 d [2] = 2 。还父[2] = 1 。
- d [1] + 成本[1] [4] = 4 。所以 d [4] = 4 < d [4] 。父[4] = 1 。
- d [4] + 成本[4] [6] = 9 。 d [6] = 9 < d [6] 。父[6] = 4 。
- d [2] + 成本[2] [2] = 无穷大。我们无法更新这个。
我们无法更新某些顶点,因为 d[u] + cost[u][v] ![StackOverflow 文档]( d[v]
条件不匹配。正如我们之前所说,我们使用最大 1 个边缘找到了从源到其他节点的路径。 <https://i.stack.imgur.com/Pkhx2.png)
我们的第二次迭代将为我们提供使用 2 个节点的路径。我们得到:
- d [4] + 成本[4] [5] = 12 < d [5] 。 d [5] = 12 。父[5] = 4 。
- d [3] + 成本[3] [4] = 1 < d [4] 。 d [4] = 1 。父[4] = 3 。
- d [3] 保持不变。
- d [4] 保持不变。
- d [4] + 成本[4] [6] = 6 < d [6] 。 d [6] = 6 。父[6] = 4 。
- d [3] 保持不变。
我们的图表看起来像:
我们的第 3 次迭代只会更新顶点 5 ,其中 d [5] 将为 8 。我们的图表看起来像:
在此之后,无论我们进行多少次迭代,我们都将拥有相同的距离。因此,我们将保留一个标志,检查是否发生任何更新。如果没有,我们将简单地退出循环。我们的伪代码将是:
Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
d[i] := infinity
parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
flag := false
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
d[v] := d[u] + cost[u][v]
parent[v] := u
flag := true
end if
end for
if flag == false
break
end for
Return d
为了跟踪负循环,我们可以使用此处描述的过程修改我们的代码。我们完成的伪代码将是:
Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
d[i] := infinity
parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
flag := false
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
d[v] := d[u] + cost[u][v]
parent[v] := u
flag := true
end if
end for
if flag == false
break
end for
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
Return "Negative Cycle Detected"
end if
end for
Return d
打印路径:
要打印到顶点的最短路径,我们将迭代回其父级,直到找到 NULL 然后打印顶点。伪代码将是:
Procedure PathPrinting(u)
v := parent[u]
if v == NULL
return
PathPrinting(v)
print -> u
复杂:
由于我们需要放宽边缘最大 (V-1) 次,因此如果我们使用 adjacency list
来表示图,则该算法的时间复杂度将等于 O(V * E) ,其中 E 表示边的数量。但是,如果使用 adjacency matrix
来表示图形,则时间复杂度将为 O(V ^ 3) 。原因是我们可以在使用 adjacency list
时在 O(E)
时间迭代所有边缘,但是当使用 adjacency matrix
时需要 O(V ^ 2) 时间。