CODEWITHSUNDEEP
c++graphpathbreadth-first-searchshortest
Peter V
Peter V

Reputation: 71

BFS print shortest path

I am trying to implement BFS algorithm to find the shortest path on a uniformly weighted graph. The code below is a straight implementation of the BFS from here: 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;
}

Maybe I miss something, but the code does not yield the shortest path (and I don't see why should it). This function prints the path along the right angle sides, rather than "wiggle" around the hypotenuse.

Upvotes: 1

Views: 333

Answers (1)

Peter V
Peter V

Reputation: 71

Well, with the help of paper and pencil, the solution was pretty obvious (yet I can not prove it). If I alter the neighbours iteration order each "layer", then the diagonal paths will alter it's direction and so yield the valid (shortest?) path. That being said, the inner nbr loop should look something like this:

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

Upvotes: 1

Related Questions