0

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

}
Anonymous User
  • 11
  • 3
  • https://stackoverflow.com/questions/3818079/why-use-dijkstras-algorithm-if-breadth-first-search-bfs-can-do-the-same-thing?rq=1 this is a similar question – Peter T. Walker Jul 09 '21 at 16:01
  • See also [faulty generalization](https://en.wikipedia.org/wiki/Faulty_generalization). – JaMiT Jul 09 '21 at 16:09
  • 1
    Naive BFS will not work because it may reach its destination along a suboptimal path before it reaches it a long an optimal path. Your version is a little smarter than the naive version in that you keeps looking for paths even after the destination is found. The downside of your version is that it does a lot more work because it explores suboptimal paths before eventually rejecting them. – Raymond Chen Jul 09 '21 at 16:40
  • @RaymondChen so the above method can be implemented?? Or it might fail some test case? – Anonymous User Jul 09 '21 at 16:45
  • You should check the addition in `dis[node]+it.second` for overflow (it's easier with an `unisigned` rather than a signed `int`). Without the check, adding multiple distances of `(INT_MAX/2+2)` would confuse it. – pts Jul 09 '21 at 23:16

1 Answers1

1

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.

pts
  • 80,836
  • 20
  • 110
  • 183
  • i tried to run this input on the above code and it did worked fine, it returned 2. The above code is for undirected graph. – Anonymous User Jul 09 '21 at 16:38
  • The *shortestPath* method in the question implements [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue) rather than BFS, thus it is correct. – pts Jul 09 '21 at 23:12