3

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

Community
  • 1
  • 1
KGhatak
  • 6,995
  • 1
  • 27
  • 24
  • I was thinking of similar solution. If you remove the line that "Marks Finished" (u.col=BLACK), the algo would still work, I think? It might take more iterations and worse runtime to process the queue until it becomes empty (while new items are being added to queue within the iteration itself), but when the queue is empty, that indicates all vertices have got their final shortest paths. I would definitely love to learn and get corrected if my above reasonining is incorrect. – Gaurang Patel May 16 '22 at 23:39

4 Answers4

4

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 <code>Q.enqueue(s)</code>

State of the computation after first iteration:

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:

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:

Final state

Tomáš Kratochvíla
  • 723
  • 4
  • 19
  • Pls elaborate on '**that is the reason** why BFS are not used for..' - didn't get what reason you're talking about!! – KGhatak Jul 15 '16 at 07:10
  • If you use queue instead of priority queue, the algorithm will be faster and will have lower complexity. However, for some weighed graphs will not compute shortest distance. The priority queue enables Dijkstra's algorithm to select the next vertex so as to ensure shortest distance is computed for every visited (black) vertex. If FIFO queue is used instead, it will not be able to deal with arbitrary edge weights. You can find the counterexample on even small weighted graph with a circle. – Tomáš Kratochvíla Jul 15 '16 at 07:21
  • I've tested with cycles and self-loop's. I'm unable to understand what 'arbitrary' edge-weight means. Would you pls provide a counterexample! – KGhatak Jul 15 '16 at 07:34
  • Awesome!! I realized the shortcoming. Before marking a node black, we must ensure it is reached by one of the shortest paths; and this cannot be done unless we take some greedy steps (which is priority queue in Dijkstra’s). In your counterexample, we’re marking ‘F’ black without reaching to it by any shortest path. Very nicely put. Thanks a lot!! – KGhatak Jul 15 '16 at 09:20
  • 1
    @TomášKratochvíla It's not true. you can compute shortest distance with normal queue. and it's SPFA. only downside is SPFA has worse complexity. – CodingLab Mar 29 '20 at 10:11
2

I used to have same confusion. Check out SPFA algorithm. When the author published this algorithm back in 1994, he claimed it has a better performance than Dijkstra with O(E) complexity, which is wrong.

You can treat this algorithm as an variation/improve of Bellman-Ford. Worst case complexity is still O(VE), since one node may be add/remove from the queue multiple times. But for random sparse graph, it definitely outperforms original Bellman-Ford since it skip lots of unnecessary relaxing steps.

Although this name "SPFA" seems not well accepted in academia, upon published it became very popular among ACM students due to its simplicity and ease to implement. Performance wise Dijkstra is preferred.

Shaunseph
  • 21
  • 4
1

It looks like you implemented Dijkstra's classical algorithm, without a heap. You are going through the matrix through each edge and then seeing if you can improve the distance.

MathBunny
  • 896
  • 1
  • 8
  • 16
  • Yes, I indeed dropped a min-heap and found that run time is better than Dijkstra's (though I did it independently without learning Dijkstra’s algo.). Further on run-time, Wiki says, with adjacency list representation of G, it is Theta((|E| + |V|) log |V|) as opposed to wee better O(|E| + |V| ) for mine. I also don’t get why BFS algo. are virtually unheard of for weighted graphs. – KGhatak Jul 15 '16 at 07:07
  • @KGhatak your algorithm cannot be **better** than Dijkstra. – CodingLab Mar 29 '20 at 10:16
0

Normally people say it's BFS when there is no edge weight.

  • BFS: graph with constant edge weight.

  • Dijkstra: graph with edge weights (can handle some negative edges if
    it doens't have negative cycle)

  • Bellman-ford and SPFA: graph with negative cycle.

Your code is Dijkastra or SPFA variant and not a simple BFS (although it IS based on BFS based alrorithm)

CodingLab
  • 1,441
  • 2
  • 13
  • 37