[blvckphvroh]

My implementation of breadth first search isn't returning the correct number for the shortest steps. I can't seem to figure out why. At first I assumed it was something to do with the way I was using the steps counter, but that seems right to me. Any insight would be greatly appreciated:

struct vertices{
    int value;
    int parent;
    int visited;
    int distance;
    
};


int BFS(vertices *v, int **adj_matrix, int num_nodes)
{
    int target;
    vertices current;
    bool found = false;
    int steps = 0;
    int size = 0;
    
    cin >> target >> num_nodes;
    adj_matrix [num_nodes][num_nodes];
    deque<vertices> q;

    // Mark all the vertices as not visited
    for(int i = 0; i < num_nodes; i++){
        v[i].visited = 0;
        v[i].distance = 0;
        v[i].parent = 0;
    }
    
    v[0].visited = 1;
    v[0].distance = 0;
    q.push_front(v[0]);
    
    while(!q.empty()){
        current = q.front();
        q.pop_front();
        
        for(int i=0; i<num_nodes; i++){
            if(adj_matrix[current.value][i] ==1){
                if(v[i].visited == 0){
                     steps++;
                    v[i].visited = 1;
                    v[i].distance = current.distance + 1;
                    v[i].parent = current.value;
                    q.push_back(v[i]);
                   
                }
              
                if(current.value == target){
                    break;
                }
            }
        }
  
    
    }
 
    return steps;
}

[Skydiver]

I suggest testing with small graphs and then increasing the size until you can reproduce the problem. In all cases, debug -- don't just run -- the code. Step through it with the debugger and verify that you paper computations match up with the values the program is coming up with.

[mojo666]

I think you need to move your check if(current.value==target) to the front of the while loop. Currently, once you reach the target, you continue to look for adjacent records and add them to the queue. I'm pretty sure this is not needed and can be contributing to extra steps.