I modified BFS to find shortest path in weighted undirected graph instead using Dijkstra’s algo and it worked

  breadth-first-search, c++, data-structures, dijkstra, graph

To find shortest path in undirected weighted graph I was comparing BFS and dijkstra’s algo
to understand why we need priority queue.

I wrote some code modifying BFS to find the shortest path to all nodes in a given graph.

Problem link :- https://practice.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1#

The below code got accepted on GeeksForGeeks that I wrote instead of dijkstra algo :-

 vector <int> dijkstra(int vertices, vector<vector<int>> graph[], int src)
  {
   // modified bfs

  vector<int> dist(vertices + 1,INT_MAX);
    queue<int> nodes;
    nodes.push(src);
    dist[src] = 0;
    while(!nodes.empty()){
        int curNode = nodes.front();
        nodes.pop();
        for(auto adjNode : graph[curNode]){
            if(dist[adjNode[0]] > dist[curNode] + adjNode[1] ){
                dist[adjNode[0]] = dist[curNode] + adjNode[1];
                nodes.push(adjNode[0]);
            }
        }
    }
    return dist;
}
 

Ques:- Although it got accepted at GeeksForGeeks , I was wondering maybe it is wrong as GeeksForGeeks maybe having a limited number of test cases?

Ques:- Or if it is a correct method , then what is the time complexity ?
(wondering maybe because of more time complexity than dijkstra algo above approach is not used)

Source: Windows Questions C++

LEAVE A COMMENT