算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

第一章 Dijkstra

一、Dijkstra求最短路I

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

$1 \leq n \leq 500$ ,
$1≤m≤10^5$ ,
图中涉及边长均不超过10000。

输入样例：

输出样例：

2. 思路分析

算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd

定义 $d i s t$ 数组来保存每一个点到起点的距离，初始化每个点的 $d i s t$ 值为正无穷，第一个点的 $d i s t$ 值为0；
寻找还未确定最短路的点中路径最短的点 $t$ ；
对 $t$ 的所出边执行松弛操作，即更新邻点的最小距离；
重复步骤2、3，直到进行 n 次迭代；
最后，如果第 n 个点的 $d i s t$ 值为正无穷，表示不存在最短路，否则输出第 n 个点的 $d i s t$ 值即可。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; //稠密图用邻接矩阵来存储
int dist[N]; //用于记录每一个点距离第一个点的距离
bool st[N];  //用于记录该点的最短距离是否已经确定

int dijkstra()
{
    //初始化距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; //第一个点的距离为0
    
    //有n个点所以要进行n次迭代
    for (int i = 0; i < n; i ++)
    {
        //将t设置为-1 代表Dijkstra算法适用于不存在负权边的图
        int t = -1; //t存储当前访问的点
        for (int j = 1; j <= n; j ++) //j代表从1号点开始
            if (!st[j] && (t == - 1 || dist[t] > dist[j])) //寻找还未确定最短路的点中路径最短的点
                t = j;
        
        //依此更新每个点到临界点的距离
        for (int j = 1; j <= n; j ++)
           dist[j] =  min(dist[j], dist[t] + g[t][j]);
          
        st[t] = true;
    }
    //如果第n个点的距离为无穷大，即不存在最短路径
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;
    
    //初始化图，因为是求最短路径，所有每个点初始化为无限大
    memset(g, 0x3f, sizeof g);
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        
        //如果图中出现重边，则保留最短的一条边
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra() << endl;
    
    return 0;
}

二、 Dijkstra求最短路 II

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

$1≤n,m≤1.5×10^5$ ,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10^9。

输入样例：

输出样例：

2. 思路分析

$D ijk s t r a$ 算法的 堆优化——用优先队列维护被更新的点的集合。

创建一个 $p ai r$ 类型的小根堆 heap{距离, 点}，这样距离最小的点一定在堆顶；
初始化，将第一个点的 $d i s t$ 值设置为0，其他点的 $d i s t$ 值为正无穷，把{0, 1}入堆；
弹出距离最短的堆顶元素 $u$ ，若 $u$ 扩展过则跳过，否则打标记；
对 $u$ 的所有出边进行松弛操作，把 {d[v], v} 压入堆中；
重复步骤3、4，知道队列为空；
最后，如果第 n 个点的 $d i s t$ 值为正无穷，表示不存在最短路，否则输出第 n 个点的 $d i s t$ 值即可。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//存储距离和节点编号
typedef pair<int, int> PII;

const int N = 1e6 + 10;


int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];//存储距离
bool st[N]; //存储状态

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); //初始化所有点的距离为无穷大
    dist[1] = 0; //第一个点的距离为0
     
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆
    heap.push({0, 1}); //插入第一个点，距离是0
    
    while(heap.size())
    {
        //取出堆顶元素，即距离最短的点
        auto t = heap.top();
        heap.pop();
        
        //ver是节点编号，distance是距离源点的距离
        int ver = t.second, distance = t.first;
        
        if(st[ver]) continue; //如果该点距离已经确定，则跳过该点
        st[ver] = true; //对该点做标记
        
        //更新ver所指向的节点距离
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j}); //距离变小，则入堆
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    
    return 0;
}

第二章 bellman-ford

一、有边数限制的最短路

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 $n, m, k$ 。

接下来 m 行，每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

点的编号为 $1 \sim n$ 。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

$1 \leq n, k \leq 500$ ,
$1 \leq m \leq 10000$ ,
$1 \leq x, y \leq n$ ，
任意边长的绝对值不超过 10000。

输入样例：

输出样例：

2. 思路分析

用结构体来保存到点和边权， $d i s t$ 数组保存点到源点的距离；
初始化：设置所有的 $d i s t$ 值为正无穷，第一个点的 $d i s t$ 值为 0；
进行 $k$ 次循环，先对 $d i s t$ 数组进行备份，再对所有边进行一次松弛操作；
最后，如果 dist[n] > 0x3f3f3f3f / 2，表示不存在最短路，否则输出 dist[n]即可。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 10010;

//保存每条边
struct Edge 
{
    int a, b, c;
}edges[M]; 

int n, m, k;
int dist[N];
int back[N]; //备份数组防止串联

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < k; i ++) //k次循环
    {
        memcpy(back, dist, sizeof dist); //对dist数组进行备份
        for (int j = 0; j < m; j ++) //遍历所有边
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], back[e.a] + e.c); //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    bellman_ford();
    
    //由于存在负权边，所以第n个点的dist值可能被更新，即小于无穷大
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n] << endl;
    
    return 0;
}

第三章 spfa

一、spfa求最短路

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

$1≤n,m≤10^5$ ,
图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

2. 思路分析

核心： 只有本轮被更新的点，其出边才有可能引起下一轮的松弛操作，因此用队列来维护被更新的点的集合。

初始化：设置所有的 $d i s t$ 值为正无穷，第一个点的 $d i s t$ 值为 0；建立 $s t$ 数组来标记点是否在队列中；将第一个点压入队列中；
队头出队，对所有出边进行松弛操作，如果被更新的点没有在队列中，则将点压入队尾；
重复操作2直到队列为空；
最后，如果第 n 个点的 $d i s t$ 值为正无穷，表示不存在最短路，否则输出第 n 个点的 $d i s t$ 值即可。

spfa图解：

给定一个有向图，如下，求A~E的最短路

算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd

源点A首先入队，然后A出队，计算出到BC的距离会变短，更新距离数组，BC没在队列中，BC入队

算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd

B出队，计算出到D的距离变短，更新距离数组，D没在队列中，D入队。然后C出队，无点可更新
D出队，计算出到E的距离变短，更新距离数组，E没在队列中，E入队
E出队，此时队列为空，源点到所有点的最短路已被找到，A->E的最短路即为8

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N]; //标记点是否在队列中

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa()
{
    //初始化dist数组
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        //对所有出边进行松弛操作
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i]; //更新最短距离
                //如果被更新的点没有在队列中，则压入队尾
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    int t = spfa();
    
    if (t == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl;
    
    return 0;
}

二、spfa判断负环

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

$1 \leq n \leq 2000$ ,
$1 \leq m \leq 10000$ ,
图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

Yes

2. 思路分析

初始化：设置所有的 $d i s t$ 值为正无穷，第一个点的 $d i s t$ 值为 0；建立 $s t$ 数组来标记点是否在队列中；将第一个点压入队列中；
队头出队，对所有出边进行松弛操作，如果被更新的点没有在队列中，则将点压入队尾；
重复操作2直到队列为空；
用 $c n t [x]$ 记录当前点到源点最短路的边数，由于初始化每个点到源点的距离为0，只要它能再走n步，即 cnt[x] >= n。则表示该图中一定存在负环，由于从源点到 $x$ 至少经过 $n$ 条边时，则说明图中至少要有 n + 1 个点，表示一定有点是重复使用的，即存在负环。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
int cnt[N]; //记录点到源点最短路的边数 
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa()
{
    queue<int> q;
    
    //由于在任意点处都可能存在负环，所以将每个点压入队列
    for (int i = 1; i <= n; i ++)
    {
        st[i] = true;
        q.push(i);
    }
    
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        //对所有出边进行松弛操作
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1; //将边数+1
                
                //如果经过的边数>=n，即说明需要经过n+1个点，因此存在负环
                if (cnt[j] >= n) return true;
                //被更新的点没有被标记过，则加入队列
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (spfa()) puts("Yes");
    else puts("No");
    
    return 0;
}

第四章 Floyd

一、Floyd求最短路

1. 题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 $n, m, k$ 。

接下来 m 行，每行包含三个整数 $x, y, z$ ，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 $x, y$ ，表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

$1 \leq n \leq 200$ ,
$1≤k≤n^2$
$1 \leq m \leq 20000$ ,
图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

impossible
1

2. 思路分析

状态表示：d[i,j,k]表示从 $i$ 到 $j$ ，且中间只经过编号 1~k 的最短路径的长度。
状态转移方程： dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
f[i, j, k] 表示从 $i$ 走到 $j$ 的路径上除 $i$ 和 $j$ 点外只经过1到 $k$ 的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
因此在计算第 $k$ 层的 $f [i, j]$ 的时候必须先将第 $k - 1$ 层的所有状态计算出来，所以需要把 $k$ 放在最外层。
读入邻接矩阵，将次通过动态规划装换成从 $i$ 到 $j$ 的最短距离矩阵;

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    cin >> n >> m >> Q;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        //保存边权最小的，即处理了重边的问题
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    while (Q --)
    {
        int a, b;
        cin >> a >> b;
        
        int t = d[a][b];
        //由于有负权边的存在，所以大于INF/2即可
        if (t > INF / 2) puts("impossible");
        else cout << t << endl;
    }
    return 0;
}