浅说最短路

柏球侠 · 2025-6-4 20:50:55

引入
单源最短路
- Dijkstra算法
  - - 例题1——最短路
    - 分析
  - Dijkstra算法的过程
  - Dijkstra算法的时间复杂度和代码
  - Dijkstra的最短路计数
- SPFA算法
  - SPFA算法的过程
  - SPFA算法的时间复杂度和代码
  - SPFA判断负环
- 单源最短路的例题
  - - P2951 [USACO09OPEN] Hide and Seek S
    - 分析
    - P1576 最小花费
    - 分析
    - P3385 【模板】负环
    - 分析
全源最短路
- Floyd算法
  - Floyd算法的过程
  - Floyd算法的时间复杂度和代码
  - Floyd寻找最小环
  - Floyd输出找到的最小环
- Johnson算法
  - Johnson算法的过程
  - Johnson算法的时间复杂度和代码
- 全源最短路例题
  - - P1690 贪婪的Copy
    - 分析
    - P10927 Sightseeing trip
    - 分析
    - P5905 【模板】全源最短路（Johnson）
    - 分析

引入

我们在信息学奥赛中，时常会遇到让我们求图上最短路的问题，之前我们可以敲dfs或bfs，但是这两个一个时间复杂度太大了，一个有限制条件，所以说我们还不如重新研究一个算法，所以这就有了最短路算法。
但是这里有个点值得注意，最短路算法不仅仅可以用于解决最短路，还可以用于解决一些不等式（组）求解的问题，也就是我们经常说的差分约束。
友情提示：在学习这篇之前，请先学习图论基础章
单源最短路

如果说，我们只想求一个点到另一个点或者说一个点到其他所有点的最短路的话，这也就是在求单源最短路，一般情况下，单源最短路会用两种算法解决，一个是Djikstra，另一个是SPFA，这两个算法都可以在较快的时间复杂度内解决，但是都有一些细微的差别，下面我们会具体来讲。
Dijkstra算法

我们还是以一道例题入手。
例题1——最短路

题目描述
给一张有 \(n\) 个点 \(m\) 条边的带权有向图，求从 \(1\) 到 \(n\) 的最短路长度
输入格式
第一行有两个正整数 \(n\) , \(m\) \((1\le n,m \le 2\times 10^5)\)
接下来有 \(m\) 行，每行有3个整数 \(u,v,w\, (1\le u,v \le n，w\le 1000)\) 表示一条从 \(u\) 到 \(v\) 的权值为 \(w\) 的边。
输出格式
输出一个整数，表示最短路的长度，如果不存在，则输出 \(No \,\ solotion\)
样例输入

5 10
3 2 8
5 4 7
1 4 8
2 5 3
3 4 8
3 5 2
4 3 6
4 1 1
5 3 6
5 1 9

复制代码

样例输出

16

复制代码

分析

如果说我们拿到这道题会怎么做？硬跑dfs？这样的时间复杂度是一定不行的。所以说我们这里就要采用Dijkstra算法。
Dijkstra算法的过程

我们将所有的点分成两个集合，一个是已经求到最小值的（我们记为 \(V\) )，另一个是还没有求到最小值，也就是说还没有确定答案的（我们记为 \(E\)），我们再记 \(dis\) 为答案数组。
首先初始话 \(dis\) 数组为正无穷。然后 \(dis[st]\) 为0 （\(st\) 为起始点）
我们从 \(E\) 中取出一个离起点最近的点（记为 \(u\)），将他放入 \(V\)，然后遍历 \(u\) 连接到的点（记为 \(v\)），根据 \(u\) 的答案来更新 \(v\) 的答案（这里的 \(v\) 是没有在集合 \(V\) 中的，这个操作就是被我们叫做的“松弛操作”），并将更新过的答案放入 \(E\) 中。重复循环这个过程，直到 \(E\) 为空集，此时 \(n\) 的答案就是我们想要的。
这样听起来是不是有点抽象，我们举个例子。

记 \(mp[x][y]\) 为从 \(x\) 到 \(y\) 的路径长度。
我们先初始化所有的 \(dis\) 数组为正无穷。\(dis[1]\) 为0。

从1开始，先把1放入集合 \(V\) ，当前可以去的点有2，3，5；
\(\because\,dis[2]>dis[1]+mp[1][2]\) \(\therefore dis[2]=dis[1]+mp[1][2]=3\)
同理 \(dis[3]=dis[1]+mp[1][3]=3,dis[5]=dis[1]+mp[1][5]=6\)
此时将上述两个放入集合 \(E\) 中。\(E=\{2,3,5\}\)

<blockquote>
从集合 \(E\) 中拿出 2，先把2放入集合 \(V\) ，从2开始，可以去的点有4，5；
\(\because\,dis[4]>dis[2]+mp[2][4]\) \(\therefore dis[4]=dis[2]+mp[2][4]=5\)
\(\because\, dis[5]>st; fi(); for (int i=1;i>u>>v>>w; mp.push_back({v,w}); } dijkstra(st); for (int i=1;i=MAXN)couts>>t; fi(); for (int i=1;i>u>>v>>w; mp.push_back({v,w});//有向图 } spfa(s); coutm>>s>>t; fi(); for (int i=1;i>u>>v>>w; mp.push_back({v,w}); } spfa(s); if (dis[t]>=1e18)cout>st>>ed; dijkstra(ed); printf("%.8lf",dis[st]); return 0;}[/code]P3385 【模板】负环

题目描述
给定一个 \(n\) 个点的有向图，请求出图中是否存在从顶点 \(1\) 出发能到达的负环。
负环的定义是：一条边权之和为负数的回路。
输入格式
本题单测试点有多组测试数据。
输入的第一行是一个整数 \(T\)，表示测试数据的组数。对于每组数据的格式如下：
第一行有两个整数，分别表示图的点数 \(n\) 和接下来给出边信息的条数 \(m\)。
接下来 \(m\) 行，每行三个整数 \(u, v, w\)。

若 \(w \geq 0\)，则表示存在一条从 \(u\) 至 \(v\) 边权为 \(w\) 的边，还存在一条从 \(v\) 至 \(u\) 边权为 \(w\) 的边。
若 \(w < 0\)，则只表示存在一条从 \(u\) 至 \(v\) 边权为 \(w\) 的边。

输出格式
对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。
输入输出样例 #1
输入 #1

const int INF=1e4+10;
struct Node{
int v, w;
};
vector<Node> mp[INF];
int dis[INF],used[INF];
int n;
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
for (int i=1;i<=n;i++){
int u=0,minn=INT_MAX;
for (int j=1;j<=n;j++){
if (!used[j]&&dis[j]<minn)u=j,minn=dis[j];
used[j]=1;
}
int len=mp[u].size();
for (int i=0;i<len;i++){
int v=mp[u][i].v,w=mp[u][i].w;
if (dis[v]>dis[u]+w)dis[v]=dis[u]+w;
}
}
}

复制代码

输出 #1

#include<bits/stdc++.h>
using namespace std;
const long long INF=2e5+10,MAXN=1e18;
struct Node{
long long p,num;
bool operator <(const Node &b)const{
return num>b.num;
}
};
priority_queue<Node> q;
long long n,m,st,dis[INF],used[INF];
vector<Node> mp[INF];
void dijkstra(int x){
dis[x]=0,q.push({x,0});
while (!q.empty()){
int u=q.top().p;
q.pop();
if (used[u]!=0)continue;
used[u]=1;
int len=mp[u].size();
for (int i=0;i<len;i++){
long long v=mp[u][i].p,w=mp[u][i].num;
if (dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
}
void fi(){
for (int i=0;i<=n;i++)mp[i].clear();
for (int i=0;i<=n;i++)dis[i]=MAXN;
for (int i=0;i<=n;i++)used[i]=0;
}
int main(){
int T;
cin>>T;
while (T--){
cin>>n>>m>>st;
fi();
for (int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
mp[u].push_back({v,w});
}
dijkstra(st);
for (int i=1;i<=n;i++){
if (dis[i]>=MAXN)cout<<2147383647<<" ";
else cout<<dis[i]<<" ";
}
cout<<endl;
}
return 0;
}

复制代码

说明/提示
数据规模与约定
对于全部的测试点，保证：

\(1 \leq n \leq 2 \times 10^3\)，\(1 \leq m \leq 3 \times 10^3\)。
\(1 \leq u, v \leq n\)，\(-10^4 \leq w \leq 10^4\)。
\(1 \leq T \leq 10\)。

分析

这道题其实就是非常裸的负环的模版，只不过这里要注意一下数组的清空和邻接表的清空，要不然就寄完了。

#include<bits/stdc++.h>
using namespace std;
struct Node{
int p,num;
bool operator <(const Node &a)const{
return num>a.num;
}
};
const int INF=1e5+10;
vector<int> mp[INF];
priority_queue<Node> q;
int dis[INF],ans[INF],used[INF];
void dijkstra(int x){
dis[x]=0,ans[x]=1,q.push({x,dis[x]});
while (!q.empty()){
int u=q.top().p;q.pop();
if (used[u])continue;
used[u]=1;
int len=mp[u].size();
for (int i=0;i<len;i++){
int v=mp[u][i];
if (dis[v]>dis[u]+1){//情况1
dis[v]=dis[u]+1,ans[v]=ans[u];
q.push({v,dis[v]});
}else if (dis[v]==dis[u]+1){//情况2
ans[v]+=ans[u];
ans[v]%=100003;
}
}
}
}
int n,m;
void fi(){
for (int i=0;i<=n;i++){
dis[i]=1e8;
}
}
int main(){
cin>>n>>m;
fi();
for (int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
dijkstra(1);
for (int i=1;i<=n;i++){
cout<

复制代码

全源最短路

如果说我们想要求任意两点之间的最短路，那么就等于我们要求的是全源最短路，对于全源最短路，我们经常会有两种算法可以解决，一种是Floyd，另一种是Johnson，这两个算法和上面的两个算法不同的是，这两个算法可以使用在任意图上，不必在意是否有负权或负环。
Floyd算法

可能你在自学的时候，会发现一些博客或者书中讲的是这样的：

每次枚举一个中间的转折点，然后再枚举另外两个点，然后答案就是两个点经过中转点转移走后的答案的最小值，也就是说枚举中转点 \(k\) 和另外两个点 \(i\)，\(j\)，答案就是 \(dis[j]=\min(dis[k]+dis[k][j],dis[j])\)

非常尴尬的说，这样的理解是完全错误的，我们可以注意到，动态规划是要从已知量到未知量，但是这里的 \(dis[k]\) 和 \(dis[k][j]\) 是两个不确定的答案，这两个不一定是正确答案，甚至于说后来可能还会被更新，这就一定是不正确的。
咱就说，有没有一种可能，Floyd算法原本是三维的？
Floyd算法的过程

因为是dp，我们可以将d的状态定义成经过的点的编号不超过 \(k\)，也就是说，我们的dp数组应该长成这样

\[dp[k][j]//从i到j的路径上的编号不超过k的最小值\]
如果是这样理解的话，我们转移的时候就有一下两种情况

换句话说就是，在所有点的编号都是小于等于 \(k\) 的前提下时，从 \(i\) 到 \(j\) 的最短路经不经过 \(k\) 这个点。
基于此，我们就可以非常轻松的得到以下两种状态转移的方式。

\[dp[k][j]=dp[k-1][j] //如果当前这条路径上的点都小于k \\ \, \\dp[k][j]=dp[k-1][k]+dp[k-1][k][j] //因为有点k，所以以点k为分界点，将左右两边的最优解加起来\]
注意：这里的把看作为转换点和网络上的是不一样的，这里是有限制的。
因为这两种方式都是可以的，所以我们把这两个状态转移方程合并一下就可以得到以下内容。

\[dp[j][k]=min(dp[k-1][j],dp[k-1][k]+dp[k-1][k][j])\]
此时我们的边界条件是 \(dp[0][j]=mp[j]\)（不存在的边存为无无穷大）
但是这样的空间是三维的，忒多了，指定要爆，所以说我们要优化一下。
可以发现，我们只做了一次dp，并且k的值是递增的，也就是说，每一次的答案只和前一次的答案有关系，所以说我们就可以把第三维给滚动掉，这样我们只需要开一个二维数组就行了。我们也可以顺手证明一下：

对于给定的 \(k\)，当更新 \(dp[k][j]\) 时，他所涉及的元素总是来自 \(dp[k-1]\) 这个长数组的第 \(k\) 行和第 \(k\) 列。然后我们可以发现，对于给定的 \(k\)，当更新 \(dp[k][k][j]\) 或 \(dp[k][k]\)，总是不会发生数值更新，因为按照公式 \(dp[k][k][j] = min(dp[k-1][k][j], dp[k-1][k][k]+dp[k-1][k][j])\),\(dp[k-1][k][k]\) 为 0，因此这个值总是 \(dp[k-1][k][j]\)，对于 \(dp[k][k]\) 的证明类似。
因此，如果省略第一维，在给定的 \(k\) 下，每个元素的更新中使用到的元素都没有在这次迭代中更新，因此第一维的省略并不会影响结果。

Floyd算法的时间复杂度和代码

很显然可以发现，这个是非常铁的三层循环，并且常数非常小，所以说时间复杂度是铁打的 \(\cal O(n^3)\)
[code]for (int k=1;k>y>>z; a[x][y]=a[y][x]=min(a[x][y],z); dis[x][y]=dis[y][x]=a[x][y]; } for (int k=1;k

账号		自动登录	找回密码
密码			立即注册