CODEWITHSUNDEEP
c++data-structuresgraphbreadth-first-searchdijkstra
Anonymous User
Anonymous User

Reputation: 21

Can i use the bfs technique for finding the shortest path in an undirected weighted graph? Instead of dijkstra's algo?

So, consider the following graph,where 'this means weight'

1--'2'--2--'5'--5
|'1'    \'4'    /'1'       src=1 and destination =5
|        \     /            Therefore, output = 1+3+1=5
4--'3'-----3

So my question is can i use bsf instead of dijkstra's ,since int the tutorial that i am following said that we cannot use the bsf for weighted graph so we have use dijkstra's,but when i tried the bsf algo it worked fine. Here is the bsf code

#include<bits/stdc++.h>
using namespace std;

class Solution {

    public:
        int shortestPath(int N,vector<pair<int,int>>adj[],int src,int des){
            queue<int>q;
            vector<int>dis(N+1,INT_MAX);
            q.push(src);
            dis[src]=0;
            while(!q.empty()){
                int node = q.front();
                q.pop();
                for(auto it:adj[node]){
                    if(dis[node]+it.second<dis[it.first]){
                        dis[it.first]= dis[node]+it.second;
                        q.push(it.first);
                    }
                }
            }
            return dis[des];
        }
};



int main(){
    int V, E;
    cin >> V >> E;

    vector<pair<int,int>> adj[V+1];

    for(int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    Solution obj;
    cout<<obj.shortestPath(V, adj,1,5);

}

Upvotes: 1

Views: 316

Answers (1)

pts
pts

Reputation: 87291

Try to find the shortest path from A to C in this graph:

A -9-> C
A -1-> B
B -1-> C

BFS will give you 9 (incorrect), Dijkstra will eventually give you 1 + 1 (correct). So to get the correct result you can't use BFS.

The shortestPath method in the question implements Dijkstra's algorithm rather than BFS, thus it is correct.

Upvotes: 1

Related Questions