加权图的 BFS 算法 - 寻找最短距离

Question

我看过很多关于这个主题的帖子（即 , post2, post3），但是 none 的帖子提供了一种算法来支持各自的查询。因此，我不确定是否接受这些帖子的答案。

在这里，我提出了一种基于 BFS 的最短路径（单源）算法，适用于非负加权图。谁能帮我理解为什么 BFS（根据下面基于 BFS 的算法）不用于此类问题（涉及加权图）！

算法：

SingleSourceShortestPath (G, w, s):
    //G is graph, w is weight function, s is source vertex
    //assume each vertex has 'col' (color), 'd' (distance), and 'p' (predecessor) 
        properties

    Initialize all vertext's color to WHITE, distance to INFINITY (or a large number
        larger than any edge's weight, and predecessor to NIL
    Q:= initialize an empty queue

    s.d=0
    s.col=GREY     //invariant, only GREY vertex goes inside the Q
    Q.enqueue(s)  //enqueue 's' to Q

    while Q is not empty
        u = Q.dequeue()   //dequeue in FIFO manner
        for each vertex v in adj[u]  //adj[u] provides adjacency list of u
             if v is WHITE or GREY       //candidate for distance update
                  if u.d + w(u,v) < v.d        //w(u,v) gives weight of the 
                                               //edge from u to v
                      v.d=u.d + w(u,v)
                      v.p=u
                      if v is WHITE
                          v.col=GREY    //invariant, only GREY in Q
                          Q.enqueue(v)
                      end-if
                  end-if
              end-if
         end-for
         u.col=BLACK  //invariant, don't update any field of BLACK vertex.
                      // i.e. 'd' field is sealed 
    end-while

运行时间：据我所知是 O(|V| + |E|) 包括初始化成本

如果此算法与任何现有算法相似，请告诉我

Answer 1

看起来你实现了 Dijkstra 的经典算法，没有堆。您正在通过每条边遍历矩阵，然后查看是否可以改善距离。

Answer 2

由于伪代码是 Dijksta 的算法，它使用 FIFO 队列而不是始终根据距离排序的优先级队列。到目前为止，每个访问过的（黑色）顶点已经计算出可能的最短距离的关键不变量不一定是正确的。这就是为什么优先队列对于计算（正）加权图中的距离是必须的。

您可以将您的算法用于未加权的图，或者通过将权重为 n 的每条边替换为由权重为 1 的边连接的 n-1 个顶点来使其不加权。

反例：

第一次Q.enqueue(s)后的计算状态：

第一次迭代后的计算状态：

此图作为反例的重要一点是 adj[u] = adj[S] = [F, M] 而不是 [M, F]，因此 F 排在 Q.enqueue(v)

前面

第二次迭代后的计算状态：

由于顶点F首先被u = Q.dequeue()出列（与使用距离优先队列时不同），本次迭代不会更新任何距离，F将变为黑色且不变量会被侵犯。

最终迭代后的计算状态：

Answer 3

我曾经也有过同样的困惑。查看 SPFA 算法。当作者在 1994 年发布这个算法时，他声称它具有比具有 O(E) 复杂度的 Dijkstra 更好的性能，这是错误的。

您可以将此算法视为 Bellman-Ford 的 variation/improve。最坏情况下的复杂度仍然是 O(VE)，因为一个节点可能 add/remove 多次来自队列。但是对于随机稀疏图，它绝对优于原始的 Bellman-Ford，因为它跳过了很多不必要的放松步骤。

虽然这个名字 "SPFA" 在学术界似乎不太被接受，但由于其简单易用，一经发布就在 ACM 学生中广受欢迎。性能明智的 Dijkstra 是首选。

Answer 4

一般人说没有边权重的时候就是BFS

BFS: 具有恒定边权重的图。
Dijkstra：带边权的图（如果
可以处理一些负边它没有负循环）
Bellman-ford 和 SPFA：负循环图。

您的代码是 Dijkastra 或 SPFA 变体，而不是简单的 BFS（尽管它是基于基于 BFS 的算法）

加权图的 BFS 算法 - 寻找最短距离

A BFS Algorithm for Weighted Graphs - To Find Shortest Distance

algorithm

graph

breadth-first-search

shortest-path

weighted-graph