4

在具有负和正权重的有向图中使用下面的 SPFA 算法，我们如何检测负循环？

procedure Shortest-Path-Faster-Algorithm(G, s)

  1    for each vertex v ≠ s in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    push s into Q
  5    while Q is not empty
  6        u := pop Q
  7        for each edge (u, v) in E(G)
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    push v into Q
4

2 回答 2

5

SPFA 每次看到“更好”的边缘时都会将新节点放入队列中，以最小化您的总距离，这只是 Bellman-Ford 的更好修剪。Bellman-Ford 算法已经证明非负加权循环的最大值为|V| - 1 条边。

因此，要检查一个循环是否为负权重，您只需要检查您是否至少使用了|V| SPFA 运行期间的边缘。换句话说，检查你是否至少访问过同一个节点|V| 次。

这是附加的伪代码：

procedure SPFA(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
        visits(v) := 0
    d(s) := 0
    push s into Q
    while Q is not empty
        u := pop Q
        visits(u) := visits(u) + 1                      // increment visit count
        if visits(u) < |V| then                         // relaxation step
            for each edge (u, v) in E(G)
                if d(u) + w(u, v) < d(v) then
                    d(v) := d(u) + w(u, v)
                    if v is not in Q then
                        push v into Q

但是，请注意，这不会得到所有属于负权重循环的节点。要获取属于负权重循环的所有节点，请执行 DFS 或 BFS 以标记所有可从u到达的节点，其中visits( u ) = |V| .

这是最终修改后的伪代码：

procedure DFS(G, u, visited)
    if visited(u) = false then
        visited(u) := true
        for each edge (u, v) in E(G)
            DFS(G, v, visited)

procedure SPFA(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
        visits(v) := 0
    d(s) := 0
    push s into Q
    while Q is not empty
        u := pop Q
        visits(u) := visits(u) + 1                      // increment visit count
        if visits(u) < |V| then                         // relaxation step
            for each edge (u, v) in E(G)
                if d(u) + w(u, v) < d(v) then
                    d(v) := d(u) + w(u, v)
                    if v is not in Q then
                        push v into Q
    for each vertex u in V(G)
        visited(u) := false
    for each vertex u in V(G), where visits(u) = |V|
        DFS(G, u, visited)
    for each vertex u in V(G), where visited(u) = true
        d(u) := -∞
于 2014-11-06T03:35:44.397 回答
1

我的回答内容大部分取自这篇文章。

在 Bellman-Ford 算法的原始论文中，证明了在没有负循环的有向加权图中，最短路径的长度最多为 |V|-1 条边。

我们可以利用这一事实来检测 SPFA 的负循环。我们只需要保留一个额外的数组来存储每个顶点的当前最短路径的长度（以边数计）。一旦这个数字达到 |V| 对于任何顶点，我们知道图中存在负循环。

下面是使用 SPFA 检测负循环的伪代码。它已被修改，使得每个顶点的起始“最短路径”为 0。这相当于创建一个虚构的源s ，并将s连接到权重为 0 的边的每个顶点。这样可以确保您可以找到负循环，即使该图未连接。

function SPFA(G):
    for v in V(G):
        len[v] = 0
        dis[v] = 0
        Queue.push(v)
    while !Queue.is_empty():
        u = Queue.pop()
        for (u, v) in E(G):
            if dis[u] + w(u, v) < dis[v]:
                len[v] = len[u] + 1
                if len[v] == n:
                    return "negative cycle detected"
                dis[v] = dis[i] + w(u, v)
                if !Queue.contains(v):
                    Queue.push(v)
    return "no negative cycle detected"

如果你想找到负循环，你可以阅读上面链接的文章，因为它也解决了这个问题。

于 2020-05-01T13:51:23.990 回答