CODEWITHSUNDEEP
algorithmc++11shortest-pathbreadth-first-search
asad_nitp
asad_nitp

Reputation: 433

finding shortest path of all nodes from a given node using BFS

when i increase or decrease INF value the Output Behaves Unexpectedly.. I think INF should not have any effect on the output.. length of each edge is 6 for input 1 4 2 1 2 1 3 1 the output is 6 6 -1 when I change INF to 1e8 the output is 0 0 0 

 #include<iostream>
 #include<vector>
 #include<queue>
 #include<cstring>

 using namespace std;

 #define MAX 2000
  #define INF 1000000

 vector<int> adj[MAX];
 int d[MAX];
  bool visited[MAX];

 void initialise(){
   for(int i=0;i<=MAX;i++){
  visited[i]=false;
   }
  }

  void shortestPathBfs(int start){

  queue<int> q;
   q.push(start);
     visited[start]=true;
     d[start]=0;

  while(!q.empty()){
      int p=q.front();
       q.pop();
      for(int i=0;i<adj[p].size();i++){
           int v=adj[p][i];
            if(!visited[v] && d[v]>d[p]+6){
                d[v]=d[p]+6;
                q.push(v);
               visited[v]=true;
            }
        }
       }
      }

         int main(){
         int T,N,M,S,x,y;
            cin>>T;
          while(T--){
        cin>>N>>M;
      for(int i=0;i<M;i++){
         cin>>x>>y;
          adj[x].push_back(y);
          adj[y].push_back(x);
      }
      cin>>S;

       initialise();
         memset(d,INF,sizeof(d));
         shortestPathBfs(S);

   for(int i = 1; i <=N; i++) {
        if(i == S)
            continue;
        if(d[i] >= INF)
              cout<<"-1"<<" ";
        else
            cout<<d[i]<<" ";
          }
       }

      }

Upvotes: 3

Views: 216

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51316

The problem is with

memset(d,INF,sizeof(d));

memset() only fills memory with a byte value. Here it will wind up filling the array with the least significant byte of the int value INF. To fix it, create an explicit for loop or use std::fill() instead.

Upvotes: 1

Related Questions