CODEWITHSUNDEEP
algorithmbreadth-first-searchshortest-path
codesavesworld
codesavesworld

Reputation: 793

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

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);
                }
            }
        }

Upvotes: 0

Views: 699

Answers (1)

dhakim
dhakim

Reputation: 147

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

Upvotes: 0

Related Questions