「代码随想录算法训练营」第五十二天 | 图论 part10

Floyd算法

Floyd算法用于求解多源最短路问题(求多个起点到多个终点的多条最短路径)。在前面学习的dijkstra算法、Bellman算法都是求解单源最短路的问题(即只能有一个起点)。

注意:Floyd算法对边的权值正负没有要求,都可以处理。

Floyd的核心思想是动态规划

动态规划的五部曲:

  • 确定dp数组(dp table)以及下标的含义。
  • 确定递推公式。
  • dp数组如何初始化。
  • 确定遍历顺序。
  • 举例推导dp数组。

根据动态规划的五部曲来解释Floyd算法的遍历过程。

1. 确定dp数组(dp table)以及下标的含义。

把dp数组命名为grid数组,用来来存图。

grid[i][j][k] = m表示节点i到节点j中以[i...k]集合为中间节点的最短距离为m。

2. 确定递推公式。

分两种情况:

  1. 节点i到节点j的最短路径经过节点k。
  2. 节点i到节点j的最短路径不经过节点k。

对于第一种情况:grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

对于第二种情况:grid[i][j][k] = grid[i][j][k - 1]

由于我们在求解最短路,因此对于这两种情况要取最小值:

grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1])

3. dp数组如何初始化。

grid[i][j][k] = m,表示节点i到节点j以[1...k]集合为中间节点的最短距离为m。

4. 确定遍历顺序。

从递推公式:grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1])可以看出,我们需要三个for循环,分别遍历i,j和k。而k依赖于k - 1,i和j的到并不依赖与i - 1或者j - 1等等。

其中遍历k的for循环一定是在最外面,这样才能一层一层去遍历。

暂不举例推导。

题目:97. 小明逛公园

题目链接:https://kamacoder.com/problempage.php?pid=1155
文章讲解:https://www.programmercarl.com/kamacoder/0097.小明逛公园.html
题目状态:看题解

思路:

Floyd算法

代码:

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main()
{
    int n, m, p1, p2, val;
    cin >> n >> m;

    // 因为边的最大距离是10^4
    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));
    for(int i = 0; i < m; ++i)
    {
        cin >> p1 >> p2 >> val;
        grid[p1][p2][0] = val;
        grid[p2][p1][0] = val; // 注意这里是双向图
    }
    
    // 开始Floyd
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1]);
            }
        }
    }

    // 输出结果
    int z, start, end;
    cin >> z;
    while(z--)
    {
        cin >> start >> end;
        if(grid[start][end][n] == 10005) cout << -1 << endl;
        else cout << grid[start][end][n] << endl;
    }
}

空间优化:

我们只需要记录grid[i][j][1]grid[i][j][0]就好,之后就是grid[i][j][1]grid[i][j][0]交替滚动。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));  // 因为边的最大距离是10^4

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == 10005) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}

A * 算法

Astar是一种广搜的改良版。有的是Astar是dijkstra的改良版。

其实只是场景不同而已 我们在搜索最短路的时候,如果是无权图(边的权值都是1)那就用广搜,代码简洁,时间效率和dijkstra差不多(具体要取决于图的稠密)

如果是有权图(边有不同的权值),优先考虑dijkstra。

而Astar关键在于启发式函数, 也就是影响广搜或者dijkstra从容器(队列)里取元素的优先顺序。

本博客中使用BFS版本的A*算法。

启发式函数要影响的就是队列里元素的排序。

这是影响BFS搜索方向的关键。

对队列里节点进行排序,就需要给每一个节点权值,如何计算权值呢?

每个节点的权值为F,给出公式为:F = G + H

  • G:起点达到目前遍历节点的距离
  • H:目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离就是起点到达终点的距离。

本题的图是无权网格状,在计算两点距离通常有如下三种计算方式:

  • 曼哈顿距离,计算方式: d = abs(x1-x2)+abs(y1-y2)
  • 欧氏距离(欧拉距离) ,计算方式:d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
  • 切比雪夫距离,计算方式:d = max(abs(x1 - x2), abs(y1 - y2))

x1, x2 为起点坐标,y1, y2 为终点坐标 ,abs 为求绝对值,sqrt 为求开根号,

选择哪一种距离计算方式 也会导致 A * 算法的结果不同。

动态模拟地址:https://kamacoder.com/tools/knight.html

题目:126.骑士的攻击

题目链接:https://kamacoder.com/problempage.php?pid=1203
文章讲解:https://www.programmercarl.com/kamacoder/0126.骑士的攻击astar.html
题目状态:看题解

思路:

A*算法

代码:

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int moves[1001][1001];
int dir[8][2] = {-2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2};
int b1, b2;

// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗

struct Knight
{
    int x, y;
    int g, h, f;
    // 重载运算符,从小到大排序
    bool operator<(const Knight &k) const
    {
        return k.f < f;
    }
};

priority_queue<Knight> que;

// 欧拉距离
int Heuristic(const Knight &k)
{
    // 统一不开根号,这样可以提高精度
    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
}

void astar(const Knight &k)
{
    Knight cur, next;
    que.push(k);
    while(!que.empty())
    {
        cur = que.top(); que.pop();
        if(cur.x == b1 && cur.y == b2) break;
        for(int i = 0; i < 8; ++i)
        {
            next.x = cur.x + dir[i][0];
            next.y = cur.y + dir[i][1];
            if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) continue;
            if(!moves[next.x][next.y])
            {
                moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
                // 开始计算F
                next.g = cur.g + 5; // 统一不开根号,这样可以提高精度,马走日,1*1+2*2=5
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
            }
        }
    }
}

int main()
{
    int n, a1, a2;
    cin >> n;
    while(n--)
    {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves, 0, sizeof(moves));
        Knight start;
        start.x = a1;
        start.y = a2;
        start.g = 0;
        start.h = Heuristic(start);
        start.f = start.g + start.h;
        astar(start);
        while(!que.empty()) que.pop(); // 队列清空
        cout << moves[b1][b2] << endl;
    }
    return 0;
}

最短路算法总结