CODEWITHSUNDEEP
data-structuresgraph-theorybreadth-first-searchshortest-path
Piyush Saha
Piyush Saha

Reputation: 31

Using BFS based single source shortest path for a weighted undirected graph

Here is the link to the tutorial I followed: https://www.youtube.com/watch?v=hwCWi7-bRfI&t=1106s

Here is the code :

void BFS(vector<int> adj[], int N, int src) 
{ 
    int dist[N];
    for(int i = 0;i<N;i++) dist[i] = INT_MAX; 
    queue<int>  q;
    
    dist[src] = 0;
    q.push(src); 

    while(q.empty()==false) 
    { 
        int node = q.front(); 
        q.pop();
         
        for(auto it:adj[node]){
            if(dist[node] + 1 < dist[it]){
                dist[it]=dist[node]+1;
                q.push(it);
            }
        } 
    } 
    for(int i = 0;i<N;i++) cout << dist[i] << " "; 
}

In the for loop, where we are checking if(dist[node] + 1 < dist[it]), instead of +1, can we do the weight of the edge from node to it and use this code for calculating shortest paths from a vertex to every other vertex in an undirected weighted graph?

Upvotes: 1

Views: 407

Answers (1)

kaya3
kaya3

Reputation: 51063

For most implementations of BFS, the answer is no, because the queue would end up being in the wrong order - BFS only guarantees shortest paths in unweighted graphs, because the queue order guarantees that the first time you see a node is necessarily via a shortest path to it.

For the specific implementation in your question, the answer is actually yes, because this implementation doesn't actually prohibit a node from being visited (and its neighbours added to the queue) more than once, except by comparing if the path found is longer than a previously-found one. This means that adding a node to the queue via a non-shortest path doesn't cause an incorrect result, because later the same node will be added via its shortest path, and its distance will be updated (causing its neighbours to also get updated, and so on). It just means that your algorithm can visit some nodes many times, making it inefficient; but it will actually find shortest paths.

If you fix this problem by using a priority queue instead of a queue, then you have Dijkstra's algorithm.

Upvotes: 2

Related Questions