Разбор BFS-минимальное растояние

Изучаю разные алгоритмы и наткнулся на реализацию "Breadth First Search: Shortest Reach", но не могу понять его работы, в особенности почему повсеместно вычитается 1. Буду благодарен за обьяснение.

n - количество узлов графа, m - количество связей между вузлами в графе, edges - масив начал и концов граней, s - узел с которого начинаем. еденица растояния - 6.

vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) {
    vector<int> result(n, -1);
    
    bool *visited = new bool[n];
    
    for(int i = 0; i < n; i++)
        visited[i] = false;
    
    list<int> queue;
    visited[s-1] = true;
    result[s-1] = 0;
    
    queue.push_back(s-1);
    
    while(!queue.empty())
    {
        s = queue.front();
        queue.pop_front();
        
        for(auto edge = edges.begin(); edge !=edges.end(); edge++)
        {
            int u = (*edge)[0]-1, v = (*edge)[1]-1;
            if(u == s && v!=s && !visited[v])
            {
                visited[v] = true;
                result[v]= result[u]+6;
                queue.push_back(v);
            }
            else if(u!=s && v==s && !visited[u])
            {
                visited[u] = true;
                result[u] = result[v] + 6; 
                queue.push_back(u);
            }
        }
    }
            remove_if(result.begin(), result.end(), [](int a){return a==0; });
            result.resize(n-1);
            return result;
    
}

Ответы (1 шт):

Автор решения: Neuro

Так как граф представлен в натуральной нумерации вершины 1...N, а граф работает с вершинами 0...N-1, то везде вычитается -1, чтобы перейти в нужную нумерацию, почему же BFS дает всегда правильный ответ для невзвешенных графов. BFS или поиск в ширину работает таким образом, что для каждой вершины мы сначала перебираем ее соседей, и для них по индукции результат будет dist[cur] = dist[prev]+1. По этой формуле находятся расстояния до всех верши, а массив visited гарантирует что мы не зайдем в одну и ту же вершину более одного раза. Проще визуализировать это для дерева, если мы запустим BFS от корня, то для каждой вершины мы будем перебирать его потомков, и это гарантирует нам правильное расстояние от корня до любой вершины

→ Ссылка