Does this BFS-based algorithm work for find shortest path in weighted graph

Question

I know that plain BFS search can be used for find shortest path in unweighted graph or graph with same edge weight, and Dijkstra should be used in weighted graph, and Dijkstra can be seen as a variant of BFS.

But I wonder if I push the node to the queue every time the dist[w] is updated, instead of only push once in plain BFS search, will this algorithm work for finding shortest path? I tried this algorithm on one leetcode problem, and it worked, but the leetcode problem only check limited testcase, so I cant prove the correctness of this algorithm. If the algorithm is correct, what's the time complexity?

   vector<int>dist(N + 1, INT_MAX);
        dist[start] = 0;
        queue<int>q;
        q.push(start);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto [w, cost] : g[v]){
              //  cout<<w<<" "<<cost<<endl;
                if(cost + dist[v] < dist[w]){
                    dist[w] = cost + dist[v];
                    q.push(w);
                }
            }
        }

This is a known variant of Dijkstra. It is not an actually a Dijkstra anymore it is no longer greedy, you will just turn it into a shortest path algorithm. You lose the performance benefits but it can work with negative values. — unlut
See answer by rontogiannis and comments of the answer: stackoverflow.com/questions/29715022/… — unlut
@unlut I dont think this is a variant of Dijkstra, Dijkstra extracts the shortest dist from the unknown node set everytime, so it require a priotiry_queue or scan the whole dist array everytime. but this BFS-based version push node to queue when dist is updated... — zenxy

dhakim dhakim · Accepted Answer · 2020-12-10T08:46:59

I believe you have rediscovered the Bellman-Ford algorithm, minus the necessary handling for failing out on negative weight cycles. It should run in O(|V| * |E|) time (as opposed to the O((|V| + |E|) * lg(|V|)) of Dijkstra's) assuming no negative cycles, which will infinite loop on your implementation. The good part is that it handles negative edge weights, which Dijkstra's does not. The bad part is that it is much slower.

See https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Does this BFS-based algorithm work for find shortest path in weighted graph

1 Answers