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

我看过很多帖子（即。post1 https://stackoverflow.com/questions/30409493/using-bfs-for-weighted-graphs, post2 https://cs.stackexchange.com/questions/18138/dijkstra-algorithm-vs-breadth-first-search-for-shortest-path-in-graph, post3 https://stackoverflow.com/questions/3818079/why-use-dijkstras-algorithm-if-breadth-first-search-bfs-can-do-the-same-thing）关于这个主题，但没有一篇文章提供了备份各自查询的算法。因此，我不确定是否接受这些帖子的答案。

在这里，我提出了一种基于 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

Runtime:据我所知，它是 O(|V| + |E|) ，包括初始化成本

如果该算法与现有算法类似，请告诉我

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

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

反例：

第一个之后的计算状态Q.enqueue(s):

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

该图作为反例的重要之处在于adj[u] = adj[S] = [F, M]并不是[M, F], hence F首先排队的是Q.enqueue(v)

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

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

最终迭代后的计算状态：