BFS打印最短路径

Question

我正在尝试实现BFS算法，以在均匀加权图上找到最短路径。下面的代码从这里开始是BFS的直接实现：https://www.redblobgames.com/pathfinding/a-star/introduction.html

void print_path(vector<vector<int>> & gr, int xf, int yf, int xt, int yt)
{
    /* Cell neighbours */
    const vector<pair<int,int>> nbr {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    /* route breadcrumbs */
    map<pair<int,int>,pair<int,int>> route;
    queue<pair<int,int>> q;

    /* Represent each node as a pair<int,int> */
    pair<int,int> start = {xf, yf};
    pair<int,int> end = {xt, yt};

    /* NULL node */
    route[start] = {-1, -1};
    q.push(start);

    while (!q.empty()) {
        auto current = q.front();
        q.pop();

        if (current == end) break;

        /* Iterate through all possible neighbours */
        for (const auto & n : nbr) {
            /* pair<int,int> operator+ overloaded */
            auto next = current + n;

            /* Can move to the next node and it is not yet in the route */
            if (can_move_to(next, gr) && route.find(next) == route.end()) {
                q.push(next);
                route[next] = current;
            }
        }
    }

    /* Trace back the shortest path */
    while (route[end] != pair<int,int>(-1, -1)) {
        cout << end.first << ';' << end.second << endl;
        end = route[end];
    }
    /* Print the starting node */
    cout << end.first << ';' << end.second << endl;
}

也许我错过了一些东西，但是代码并没有产生最短的路径（而且我也不知道为什么要这么做）。此功能沿直角方向打印路径，而不是在斜边周围“摆动”。

Answer 1

嗯，在纸和铅笔的帮助下，解决方案非常明显（但我无法证明这一点）。如果我更改每个“层”的邻居迭代顺序，则对角线路径将更改其方向，因此会产生有效（最短？）路径。话虽这么说，内部nbr循环应该看起来像这样：

if ((current.first + current.second) & 1) {
    /* Odd layers */
    for (auto it = nbr.begin(); it != nbr.end(); it++) {
        auto next = current + *it;
        if (can_move_to(next, gr) && route.find(next) == route.end()) {
            q.push(next);
            route[next] = current;
        }
    }
}
else {
    /* Even layers */
    for (auto it = nbr.rbegin(); it != nbr.rend(); it++) {
        auto next = current + *it;

        if (can_move_to(next, gr) && route.find(next) == route.end()) {
            q.push(next);
            route[next] = current;
        }
    }
}