当前位置：首页 > news >正文

C++图笔记（二）最短路

news 来源：原创 2024/9/19 4:40:38

单源最短路的概念：

求解最短路径的方法：

一、Dijkstra

1，原理：

2，主要特点：

3，复杂度:

4，例题加代码、

题目名称：求单源最短路

输入描述

输出描述

用例输入

用例输出

题目分析：

二，SPFA

1，原理

2，特点：

效率提升：

支持负权重边：

并行化潜力：

易于理解与实现：

内存优化：

3，复杂度

4，例题与代码

题目名称：带负权的最短路计算

描述：给定一个n个点m条边(n<=1e5,m<=2e5)的有向图，图中可能存在重边和自环，边权绝对值小于104。数据保证图中不存在负权回路。

输入描述

输出描述

三、 Bellman-Ford algorithm

初始化阶段：首先，给除起始节点之外的所有节点设置一个初始距离值，通常是无穷大（表示尚未找到该节点的最短路径），然后将起始节点的距离设为零。

松弛阶段：接着，算法会遍历图中的每一条边，尝试更新所有节点的距离值。如果经过一条边的起点到终点的路径长度小于之前已经计算出来的起点到终点的路径长度，则更新终点的距离值。这个过程会被反复执行，直到所有边都被遍历过 |V| - 1 次（其中 |V| 表示图中有多少个节点）。这个阶段称为“松弛”步骤，因为算法试图放松节点间的距离约束。

检测负权环：在最后一步，再次遍历所有的边。如果仍然能找到一条边，其能进一步减少某个节点的最短路径长度，这就意味着图中存在一个负权环（环路中总权重为负），此时算法无法准确计算出所有节点的最短路径。

特点与优势：

处理负权边：贝尔曼-福特算法最大的特点是它可以处理带负权边的有向图，这是Dijkstra算法所不具备的优势。

发现负权环：如果图中存在负权环，算法会在最后一次遍历时检测出来，这对于某些特定的应用来说非常有用。

灵活性高：算法的运行时间和复杂度依赖于图的大小，而不是依赖于边的数量，这意味着即使图中边的数量很多，贝尔曼-福特算法也能有效地工作。

应用场景：

网络路由：在互联网和其他通信网络中，贝尔曼-福特算法可以用于计算路由表中的最佳路径，特别是在可能存在临时的负成本（比如优惠折扣）的情况下。

资源分配问题：在一些经济模型或资源调度问题中，可能存在成本随着使用量增加而减少的情况（表现为负斜率的成本函数），贝尔曼-福特算法提供了一种解决方案。

时间复杂度：O(m＊n)

例题：有边数限制的最短路

单源最短路的概念：

在一颗树中，任意两点有且仅有一条路径。而在一张图中，路径可能不唯一，如果是一张带权图，此时两点之间路径上权值和最小的一条，则称为最短路。单源最短路指从一个起点出发，到其他各顶点的最短路径。

求解最短路径的方法：

一、Dijkstra

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。【节选自百度】

1，原理：

将起点的距离设置为0，将所有其他节点的距离设置为无穷大（0x3f3f3f3f），并将起点加入一个优先队列中，按照距离从小到大排序。
从优先队列中取出距离最小的节点（当前最短路径的节点），遍历与其相邻的节点。对于每个相邻节点，计算通过当前最短路径节点到达它的距离，并与已知距离进行比较。如果计算出的距离小于已知距离，则更新该节点的距离值，然后将其加入优先队列。（重复执行，直到优先队列为空或者目标节点被处理）
完成：此时，每个节点的最短路径距离都被计算出来。

2，主要特点：

主要是以起始点为中心向外层层扩展(广度优先搜索思想(BFS))，直到扩展到终点为止。核心思路是从顶点 A 往外延伸，不断更新 A 到其他点的距离，称这个操作为松弛。

3，复杂度:

朴素版本为n^2，如果边数远小于n^2,对此可以考虑堆优化（用优先队列priority_queue），取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

优点：可优化。如果经过堆优化，Dijkstra的时间复杂度能达到 O(nlogn) ，如果这个图特别稠密的话，也就是m特别大（比如完全图就是n^2），那么 O(nlogn) 是要小于m的。

缺点：不能含有负边权。

4，例题加代码、

题目名称：求单源最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值(边权小于10000)。
请你求出1号点到n号点的最短距离。如果无法从1号点走到n号点，则输出-1。

输入描述

第一行包含整数n和m(n<=1e5,m<=2e5)。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出描述

输出一个整数，表示1号点到n号点的最短距离
如果路径不存在，则输出-1。

用例输入

用例输出

题目分析：

用邻接表存图，因为边权都为正，所以可使用dijstra算法求出最短路。

进行出队标记优化

优化版：

#include<bits/stdc++.h>//万能头文件 
#pragma GCC s//优化加速*1 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fast
using namespace std;
long long read() {//快读，优化加速*2 int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}
const int N=100000;//根据题目数据范围设定 
bool vis[N];//标记数组 
vector<int > v[N];
int n,m,he[N*2],P[N*2],XT[N*2],tot,dis[N*2],ed[N*2];//（dis）记录起点的最短和距离 
void add(int x,int y,int z) {//邻接表矩阵 ++tot;P[tot]=y,ed[tot]=z,XT[tot]=he[x],he[x]=tot;
}
struct node {int ds,p;
};
bool operator < (node x,node y) {//重载运算符用于队列排序return x.ds>y.ds;
}
priority_queue<node> q;
void dij(int x) {memset(dis,0x3f,sizeof dis); dis[x]=0;q.push({0,x});//初始化 while(!q.empty()) {//当队列为空，代表顺利完成node t=q.top();//当前遍历的点q.pop();//出队int y=t.p;//当前遍历的点vis[y]=true;//使用 vis进行出队标记优化 for(int i=he[y]; i; i=XT[i]) {int ts=P[i],w=ed[i];if(vis[ts]==false&&dis[ts]>dis[y]+w) //如果该点为被标记访问且当前线路更短dis[ts]=dis[y]+w;//更新线路q.push({dis[ts],ts});//继续入队}}}
}
int main() {ios::sync_with_stdio(0);//优化加速*3 cin.tie(0);cout.tie(0);n=read();m=read();for(int i=1; i<=m; i++) {int x,y,z;x=read();y=read();z=read();add(x,y,z);}dij(1);if(dis[n]==0x3f3f3f3f) cout<<-1;//如果始终未被标记就按照题目要求输出-1 else cout<<dis[n];return 0;
}

练习题：求单源最短路

最短路径问题

二，SPFA

带负边权的最短路，对于全是正边权的图，我们可以使用dijkstra处理最短路问题。但是如果带有负边权，需考虑是否存在负权环，如果起点与终点的路径经过负权环，则没有最短路。dijkstra算法无法保证节点出队时一定得到最短路，需要重新寻找方法。

SPFA 算法是 Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

【节选自百度】

1，原理

在求解各点到起点的最小距离dis值时，若某点i产生一个更小的dis[i]，那么节点i后续指向的节点都会重新更新，因此我们可以将该点i再次入队，重新更新即可。

只有一个点在上一轮被松弛成功时，这一轮从这个点连出的点才有可能被成功松弛。

松弛的本质其实是通过一个点中转来缩短距离。所以，如果起点到一个点的距离因为某种原因变小了，从起点到这个距离变小的点连出的点的距离也有可能变小(因为可以通过变小的点中转)。(通读三遍再往下看)

所以，可以在下一轮只用这一轮松弛成功的点进行松弛，这就是SPFA的基本思想。

2，特点：

效率提升：
相比基本的Dijkstra算法，SPFA通常能够更快地找到最短路径。这是因为SPFA使用了一个额外的数据结构来存储节点的状态，并避免了多次回溯到同一个节点的情况，这使得它在处理稀疏图时比传统的Dijkstra算法更高效。
支持负权重边：
虽然SPFA主要用于无负权边的图，但在某些变体下可以适应包含一些非负权重边的图中存在负权重边的情况，但需注意的是，对于含有负权环的图，SPFA可能会陷入无限循环。因此，在实际应用中需要对输入图进行适当检查以排除这类情况。
内存优化：
SPFA通常需要较少的内存空间来运行，因为它不需要额外的空间来记录所有已访问过的节点的所有可能路径信息，而只关注当前正在探索的路径。

3，复杂度

spfa的复杂度会比dijkstra高，一般为：O(km),k是一个常数，在稀疏图中一般<=2。
但是要卡spfa也比较简单，只需尽可能多得让节点重复入队。最坏复杂度可以做到O(nm)。

优点：思想简单，可以处理负边权。

缺点：算法不稳定，最坏能被卡到0（nm），在菊花图（如下图）中要被卡

4，例题与代码

题目名称：带负权的最短路计算

描述：给定一个n个点m条边(n<=1e5,m<=2e5)的有向图，图中可能存在重边和自环，边权绝对值小于104。数据保证图中不存在负权回路。

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

输入描述

第一行包含整数n和m(n<=1e5,m<=2e5)。

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

输出描述

输出一个整数，表示1号点到n号点的最短距离
如果路径不存在，则输出-1。

用例输入

用例输出

题目分析：图中存在负边权，且无负权环。因此1-n存在最短路。
虽然n,m比较大，但是数据随机，整张图不算稠密，spfa可以尝试通过

#include <bits/stdc++.h>//万能头 
#pragma GCC s//日常优化 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fast
using namespace std;
long long read() {//日常优化 int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}
const int N =2e5;
int h[N],e[N],w[N],ne[N],idx,st[N],dis[N],q[N],H,T=-1;
void add(int a, int b, int c) {//负值e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;idx++;
}
void spfa() {T++,q[T]=1,dis[1]=0,st[1]=1;while(T>= H) {int a=q[H];H++;st[a]=0;for(int i=h[a]; i!=-1; i=ne[i]) {int b=e[i],c=w[i];if(dis[b]>dis[a]+c) {dis[b]=dis[a]+c;if(!st[b]) {T++;q[T]=b;st[b]=1;}}}}
}
int main() {ios::sync_with_stdio(0);//日常优化 cin.tie(0);cout.tie(0);memset(h, -1, sizeof h);//提前付初值 memset(dis, 0x3f, sizeof dis);提前付初值int n, m;n=read();m=read();for(int i=0; i<m; i++) {int a,b,w;a=read();		b=read();		w=read();		add(a,b,w);}spfa();if(dis[n]==0x3f3f3f3f) {cout<<"-1";} else {cout<<dis[n];}return 0;
}

三、 Bellman-Ford algorithm

贝尔曼-福特算法(Bellman-Ford algorithm)是由Richard Bellman和 Lester Ford Jr. 分别在1950年代提出的图论中一种重要的算法。它主要用于解决单源最短路径问题，尤其擅长处理包含负权边（即边的权重可以为负数）的有向图。以下是关于贝尔曼-福特算法的工作原理：【节选自百度】

遇到有限制边数的题可采用bellman_ford，从起点开始，每一次循环只更新一次，更新出新的最小值。时间复杂度为O(nm)。

首先，给除起始节点之外的所有节点设置一个初始距离值，通常是0x3f3f3f3f（表示尚未找到该节点的最短路径），然后将起始节点的距离设为零。
接着，算法会遍历图中的每一条边，尝试更新所有节点的距离值。如果经过一条边的起点到终点的路径长度小于之前已经计算出来的起点到终点的路径长度，则更新终点的距离值。这个过程会被反复执行，直到所有边都被遍历过 n- 1 次。
在最后一步，再次遍历所有的边。如果仍然能找到一条边，其能进一步减少某个节点的最短路径长度，这就意味着图中存在一个负权环（环路中总权重为负），此时算法无法准确计算出所有节点的最短路径。

特点与优势：

处理负权边：贝尔曼-福特算法最大的特点是它可以处理带负权边的有向图，这是Dijkstra算法所不具备的优势。
发现负权环：如果图中存在负权环，算法会在最后一次遍历时检测出来，这对于某些特定的应用来说非常有用。
灵活性高：算法的运行时间和复杂度依赖于图的大小，而不是依赖于边的数量，这意味着即使图中边的数量很多，贝尔曼-福特算法也能有效地工作。

时间复杂度：O(mn)

例题：有边数限制的最短路

描述

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

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

输入描述

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

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

点的编号为 1∼n。

输出描述

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

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

用例输入

用例输出

#include<bits/stdc++.h>
using namespace std;
const int M=10005;
int n,m,k，dis[505],cp[505];
struct node {int x,y,w;
} a[M];
void Bfm() {memset(dis,0x3f,sizeof dis);dis[1]=0;for(int i=0; i<k; i++) {memcpy(cp,dis,sizeof cp);for(int j=1; j<=m; j++) {int x=a[j].x,y=a[j].y,w=a[j].w;dis[y]=min(dis[y],cp[x]+w);}}
}
int main() {cin>>n>>m>>k;for(int i=1; i<=m; i++) 		cin>>a[i].x>>a[i].y>>a[i].w;Bfm();if(dis[n]>0x3f3f3f3f/2) cout<<"impossible";else cout<<dis[n];
}

四、Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名【节选自百度】

原理：

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

核心代码：

void floyd() {for(int k=1; k<=n; k++) {//模拟任何一个节点为 转折点for(int i=1; i<=n; i++) {//模拟任意两个点for(int j=1; j<=n; j++) {//if(g[i][j]>g[i][k]+g[k][j]) {//如果满足更新条件（转折后边权合更少）g[i][j]=g[i][k]+g[k][j];//更新矩阵p[i][j]=k;}}}}
}

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于Dij，也要高于SPFA.

优缺点：

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。

缺点：时间复杂度比较高，不适合计算大量数据（n>500)

时间复杂度：因为是三次循环嵌套，所以复杂度为O（n^3）

floyd算法的性质：

1，floyd通过在路径上插入中间点，从而维护整个邻接矩阵。其中，插入中间点的顺序对结果没有影响。

2，floyd算法在第执行k次插点后，最短路径上的边数一定不会超过k+1

3，在执行第k次插点操作前，所求任意两端点的最短路径上，一定不包含k以及k后的若干点。

负环的判断方法

在一个图中，若存在负环，则有些点可能不存在最短路径。即经过负环一次，最短距离都会减小。

SPFA 判断负环

某点距离变小时，更新路径边数

if(dis[y]>dis[x]+w[i]) {dis[y]=dis[x]+w[i];cnt[y]=cnt[x]+1;if(cnt[y]>=n) return true;if(!st[y]){st[y]=1;q.push(y);}
}

BELLMAN_FORD 判断负环

枚举n-1次边后，能得到最短路。

再枚举边，如果有更新，说明存在负权环

bool blmf() {memset(dis,0x3f,sizeof dis);dis[1]=0;for(int i=1; i<k; i++) {memcpy(cp,dis,sizeof cp);for(int j=1;j<=m;j++){int x=a[j].x,y=a[j].y,w=a[j].w;dis[y]=min(dis[y],cp[x]+w);}}for(int j=1;j<=m;j++){int x=a[j].x,y=a[j].y,w=a[j].w;if(dis[y]>dis[x]+w) return true;}
}