Поиск в ширину возвращает неправильную сумму

Question

Моя реализация поиска в ширину не возвращает правильное число для самых коротких шагов. Я не могу понять, почему. Сначала я предположил, что это как-то связано с тем, как я использовал счетчик шагов, но мне это кажется правильным. Любая идея будет принята с благодарностью:

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

Answer 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(v[i].value==target) //try adding these two lines of code *
                return v[i].distance;

        }

* они должны возвращать расстояние до целевого узла сразу после посещения целевого узла. Если BFS не дает правильного ответа, проверьте ваш прил. матрица, если ваш целевой узел достижим.

Answer 2

Я не понимаю, почему вы считаете steps и не вернуть v[target].distance, Предполагается, что это будет одно и то же число, не так ли? Вы говорите в своем комментарии, что когда вы вернетесь v[target].distance Вы получаете 0. Вы уверены, что сохраняете правильное значение, или есть некоторые проблемы с

v[i].visited = 1;
v[i].distance = current.distance + 1;
v[i].parent = current.value;

Или, если расстояние до вашей цели действительно 0, это означает, что вы никогда не достигнете конца, поэтому ваш steps не правильно. попытаться напечатать какое-то промежуточное значение