加权图的BFS算法-查找最短距离 [英] A BFS Algorithm for Weighted Graphs - To Find Shortest Distance

问题描述

我看过很多文章(即

之后的计算状态

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

该图重要的一个反例是 adj [u] = adj [S] = [F，M] ，而不是 [M，F] ，因此， F 首先由 Q.enqueue(v)

排队

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

由于顶点 F 首先由 u = Q.dequeue()出队(与使用距离优先级队列不同)，因此此迭代不会更新任何距离， F 将变为黑色，并且将违反不变式.

最后一次迭代后的计算状态:

I've seen quite a few posts (viz. post1, post2, post3) on this topic but none of the posts provides an algorithm to back up respective queries. Consequently I'm not sure to accept the answers to those posts.

Here I present a BFS based shortest-path (single source) algorithm that works for non-negative weighted graph. Can anyone help me understand why BFS (in light of below BFS based algorithm) are not used for such problems (involving weighted graph)!

The Algorithm:

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: As far as I see it is O(|V| + |E|) including the initialization cost

If this algorithm resembles any existing one, pls let me know

解决方案

Since the pseudocode is Dijksta's algorithm with FIFO queue instead of priority queue that is always sorted based on the distances. The crucial invariant that each visited (black) vertex has computed shortest distance possible so far will not be necessarily true. And that is the reason why priority queue is a must for computation of distance in (positively) weighted graphs.

You can use your algorithm for unweighted graphs or make it unweighed by replacing each edge with weight n with n-1 vertexes connected by edges with weight 1.

Counterexample:

State of the computation after first Q.enqueue(s):

State of the computation after first iteration:

Important for this graph to be a counterexample is that adj[u] = adj[S] = [F, M] and not [M, F], hence F is queued first by Q.enqueue(v)

State of the computation after second iteration:

Since vertex F is dequeued first by u = Q.dequeue() (unlike when distance priority queue is used), this iteration will not update any distance, F will become black and the invariant will be violated.

State of the computation after the final iteration:

这篇关于加权图的BFS算法-查找最短距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！