单源最短路径算法(假设图中存在负循环)

在阅读这个例子之前,需要对边缘松弛有一个简短的想法。你可以从这里学到它

Bellman-Ford 算法计算从单个源顶点到加权有向图中所有其他顶点的最短路径。即使它比 Dijkstra 算法慢,但它适用于边缘权重为负且在图中也发现负权重周期的情况。Dijkstra 算法的问题是,如果存在负循环,则会一次又一次地继续循环并继续减小两个顶点之间的距离。

该算法的思想是以一些随机顺序逐个遍历该图的所有边缘。它可以是任何随机顺序。但是你必须确保,如果 uv (其中 uv 是图中的两个顶点)是你的一个命令,那么必须有一个从 uv 的边。通常它直接取自给定输入的顺序。同样,任何随机顺序都可以。

选择顺序后,我们将根据放松公式放松边缘。对于从 uv 的给定边缘 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 的较短路径。稍后我们将需要它来打印从到目标顶点的最短路径。 **** ****

我们来看一个例子。我们有一个图表: StackOverflow 文档

我们选择 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 [] 的值。我们得到:

  1. d [4] + 成本[4] [5] = 无穷大 + 7 = 无穷大。我们无法更新这个。
  2. d [2] + 成本[3] [4] = 无穷大。我们无法更新这个。
  3. d [1] + 成本[1] [2] = 0 + 2 = 2 < d [2] 。所以 d [2] = 2 。还父[2] = 1
  4. d [1] + 成本[1] [4] = 4 。所以 d [4] = 4 < d [4]父[4] = 1
  5. d [4] + 成本[4] [6] = 9d [6] = 9 < d [6]父[6] = 4
  6. d [2] + 成本[2] [2] = 无穷大。我们无法更新这个。

我们无法更新某些顶点,因为 d[u] + cost[u][v] ![StackOverflow 文档]( d[v] 条件不匹配。正如我们之前所说,我们使用最大 1 个边缘找到了从到其他节点的路径。 <https://i.stack.imgur.com/Pkhx2.png)

我们的第二次迭代将为我们提供使用 2 个节点的路径。我们得到:

  1. d [4] + 成本[4] [5] = 12 < d [5]d [5] = 12父[5] = 4
  2. d [3] + 成本[3] [4] = 1 < d [4]d [4] = 1父[4] = 3
  3. d [3] 保持不变。
  4. d [4] 保持不变。
  5. d [4] + 成本[4] [6] = 6 < d [6]d [6] = 6父[6] = 4
  6. d [3] 保持不变。

我们的图表看起来像: StackOverflow 文档

我们的第 3 次迭代只会更新顶点 5 ,其中 d [5] 将为 8 。我们的图表看起来像: StackOverflow 文档

在此之后,无论我们进行多少次迭代,我们都将拥有相同的距离。因此,我们将保留一个标志,检查是否发生任何更新。如果没有,我们将简单地退出循环。我们的伪代码将是:

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) 时间。