BFS寻最短路径

图大致分为两类：有权图和无权图。

普通的bfs遍历能够直接找到无权图的最短路径。 对于有权图，bfs并不能直接找到最短路径，这时需要使用dijkstra算法。

dijkstra算法的基本思路是：维护一个最小堆，每次从中取出一个距离最小的点，然后更新它的邻居节点的距离，直到所有点的最短路径都被找到。

int bfs(vector<vector<int>> &grid)
{
    int n = grid.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<vector<int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    int steps = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; i++)
        {
            auto &cur = q.front();
            q.pop();
            int cur_x = cur[0], cur_y = cur[1];
            if (cur_x == n - 1 && cur_y == n - 1)
            {
                return steps;
            }

            for (int j = 0; j < 4; j++)
            {
                int nx = cur_x + dirs[j];
                int ny = cur_y + dirs[j + 1];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny])
                {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        steps++;
    }

    return -1;
}

或者将路径长度信息包含包含在队列节点中,此时不需要按层遍历。

int bfs(vector<vector<int>> &grid)
{
    int n = grid.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<vector<int>> q;
    q.push({0, 0, 0});
    visited[0][0] = true;
    while (!q.empty())
    {
        auto &cur = q.front();
        q.pop();
        int cur_x = cur[0], cur_y = cur[1], cur_step = cur[2];
        if (cur_x == n - 1 && cur_y == n - 1)
        {
            return cur_step;
        }

        for (int j = 0; j < 4; j++)
        {
            int nx = cur_x + dirs[j];
            int ny = cur_y + dirs[j + 1];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny])
            {
                q.push({nx, ny, cur_step + 1});
                visited[nx][ny] = true;
            }
        }
    }

    return -1;
}

在写下dijkstra算法, dijkstra 不需要进行visited标记，因为无法更新当前最短路径的节点不会被重新放入队列。

int dijkstra(vector<vector<int>> &grid)
{
    int n = grid.size();
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    dist[0][0] = 0;
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    pq.push({0, 0, 0});
    while (!pq.empty())
    {
        auto &cur = pq.top();
        pq.pop();
        int cur_dist = cur[0], cur_x = cur[1], cur_y = cur[2];
        if (cur_x == n - 1 && cur_y == n - 1)
        {
            return cur_dist;
        }

        for (int j = 0; j < 4; j++)
        {
            int nx = cur_x + dirs[j];
            int ny = cur_y + dirs[j + 1];
            if (0 <= nx && nx < n && 0 <= ny && ny < n)
            {
                int new_dist = cur_dist + grid[nx][ny];
                if (new_dist < dist[nx][ny])
                {
                    dist[nx][ny] = new_dist;
                    pq.push({new_dist, nx, ny});
                }
            }
        }
    }

    return -1;
}