单源最短路学习笔记
什么是单源最短路？
首先我们得知道什么是图
图就是这玩意儿
每条边有方向，就是有向图，否则就是无向图
根据这条规则，上面的图就是有向图
我们来看这个问题：
给出一点 s ，求 s 到所有点的最短路径（单源最短路）
怎么求单源最短路？
一般来说，求单源最短路有3种方法：Floyd , Dijkstra , SPFA
Floyd
Floyd 算法基于 DP 思想，采用邻接矩阵存边
复杂度比较高，但是常数小，容易实现。（我会说只有三个 for 吗？）
适用于所有图，不管有向无向，边权正负，但是最短路必须存在。（但是不能有负环）
具体思路：枚举所有的两两点的组合以及每一个组合的“中转点”，再进行松弛操作
设 \(a_{x,y}\) 表示 \(x \to y\) 的最短路径长度
初始化：
\[a_{x,y}=\begin{cases} x=y \ 0 \\ x\neq y \ \infty \end{cases} \]在求单源最短路径的时候就会浪费许多空间，但在求多源最短路时，复杂度仍是 $ O(n^{3}) $ ，使用范围很广
在用 Floyd 转递闭包时，我们可以考虑优化一点点：
在枚举两两的中转点时，我们枚举了很多不连通 的点
而这些点是没有贡献的
所以我们可以用 bitset 存边
每次用 _Find_next 寻找下一个联通的点
时间复杂度为 \(O(\dfrac{n^{3}}{k})\)（k是一个常数）
代码示例：
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e3+7;
int a[N][N];
int n,m,s;
inline void floyd() {
for(int k=1;k<=n;++k) // 枚举中转点
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]); // 松弛操作，即更新每两个点之间的距离
}
signed main() {
scanf("%d%d%d",&n,&m,&s);
memset(a,inf,sizeof(a));
a[s][s]=0; //初始化
for(int i=1,u,v,w;i<=m;++i) {
scanf("%d%d%d",&u,&v,&w);
a[u][v]=min(a[u][v],w); //建边,取min防止重边
}
floyd(); // 求最短路
for(int i=1;i<=n;++i)
printf("%d ",a[s][i]==inf ? 2147483647 : a[s][i]); // 输出
return 0;
}
Floyd还可以做很多有意思的题目，只是复杂度 \(O(n^{3})\)
SPFA
SPFA基于广搜思想
我们用 dis 数组记录源点到图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。
将源点入队，并重复以下步骤：
- 队首 x 出队
- 遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)
- 如果点i不在队列中，则i入队
- 若队列为空，跳出循环；否则执行1
但是这么写在有源点可以到达的负环的情况下会T飞
如何解决？
我们考虑最短路存在的时候。
由于一次松弛操作会使最短路的边数至少 \(+1\) ，而最短路的边数最多为 \(n-1\)。
所以最多执行 次松弛操作，\(n-1\) 即最多循环 \(n-1\) 次。
那么一个点入队次数 \(\geq n\) ,就会存在负环，我们就可以退出
如果图是随机的，时间复杂度为 \(O(KM)\) （K可以认为是个常数，m为边数，n为点数）
但是实际上 SPFA 的最坏复杂度是 \(O(NM)\) ，可以构造出卡 SPFA 的数据，让 SPFA 超时。
在 NOI 2018 的第一天第一题中，出题人卡了 SPFA 算法，导致 100 分变成 60 分，所以在没有负环、没有负边权、单纯求最短路径，不建议使用 SPFA 算法，而是用 Dijkstra 算法。
代码示例：
#include
#include
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e3+7;
vector > edge[N];
int cnt[N]; // 记录入队次数
int dis[N]; // 记录最短路径长度
bool inque[N]; // 判断点是否在队列中
int n,m,s;
inline bool SPFA(int s) {
memset(dis,inf,sizeof(dis));
queue q;
q.push(s);
dis[s]=0,inque[s]=true,cnt[s]=1; // 初始化
while(!q.empty()) {
int u=q.front(); // 取出队首点
q.pop();
inque[u]=false;
for(int i=0,v,w;idis[u]+w) {
dis[v]=dis[u]+w; // 进行松弛操作
if(!inque[v]) {
q.push(v); // 如果不在队列中,入队
inque[v]=true;
++cnt[v]; // 入队次数+1
if(cnt[v]>=n) // 如果入队次数>n-1
return false; // 有负环，退出
}
}
}
}
return true;
}
int main() {
scanf("%d%d%d",&n,&m,&s);
for(int i=1,u,v,w;i<=m;++i) {
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back({v,w});
}
if(!SPFA(s))
return puts("NO"),0;
for(int i=1;i<=n;++i)
printf("%d ",dis[i]==inf?2147483647:dis[i]);
return 0;
}
Dijkstra
首先，在这个算法中，有两种点，一种是已经确定最短路径的点（又称为蓝点），一种是尚未确定最短路径的点（又称为白点）。蓝点的最短路径不会再改变。
我们可以写一个代码框架：
memset(dis,inf,sizeof(dis));
dis[s]=0;
for(int i=1;i<=n;++i) {
int u=当前白点里dis值最小的;
将u设为蓝点;
for(每一条从u出去的边u->v)
dis[v]=min(dis[v],dis[u]+(u->v)这条边的权值); //更新其它点的最短路径，也叫松弛
}
这样为什么就能得出从起点出发所有点的最短路径呢？
首先，所有点都是蓝点。起点到起点的最短路径为0。
然后要找出一个当前没有到达过的点（白点）中路径最短的点，记为 u。将 u 设为蓝点（确定它的最短路径）。
有人又要问了：为什么当前最短路径最短的白点，可以转化为蓝点呢？
反正法：反正就是这样
反证法：
如果 u 的 dis 值还能更新，那么考虑从 s 到它的最短路径，其倒数第二个点，一定是现在的白点（如果它的 dis 值还能更新，又不是由蓝点更新的，自然就是由白点更新的喽）。设这个白点为 v。
那么既然 u 是当前 dis 值最小的，\(dis_{v} > dis_{u}\)，那 \(dis_v + value_{v -> u}\) 怎么会 \(> dis_{u}\) 呢？
证毕
有人又要问了：万一 $ value_{v -> u} < 0 $ 呢？
负权边这种毒瘤东西，也不是不存在的。
怎么解决呢？答案就是（ ）
无法解决！
我们的巨佬们，都没有解决这个问题（也许屏幕面前的巨佬您就能解决）。
事实上 Dijkstra 算法只能解决正权图上的最短路问题问题！
复杂度分析：外层一个循环，去除最小值一个循环，所以时间复杂度就是 $ O(n^{2}) $
我们还可以优化！！！
事实上，Dijkstra算法可以将时间复杂度降至 $ O(n \log n + m) $。
想一想，是哪个地方使算法运行得不够快？
（评测机（确信））
对于取出当前白点里dis值最小的这一步，我们可以用 堆优化 ！！！
这样就可以 AC P4779 【模板】单源最短路径（标准版）
示例代码：
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+7;
vector > edge[N];
int dis[N];
int n,m,s;
inline void Dijkstra(int s) {
priority_queue > q; // 堆优化
memset(dis,inf,sizeof(dis));
dis[s]=0;
q.push({0,s}); // 初始化
while(!q.empty()) {
pair c=q.top();
q.pop(); // 取出堆中dis最小的点
if((-c.first)!=dis[c.second]) // 如果它被修改了,就不可以被设为蓝点,先continue
continue;
int u=c.second;
for(int i=0,v,w;idis[u]+w) { // 更新
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v)); // 用负数弄小根堆
}
}
}
}
signed main() {
scanf("%d%d%d",&n,&m,&s);
for(int i=1,u,v,w;i<=m;++i) {
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back({v,w});
}
Dijkstra(s);
for(int i=1;i<=n;++i)
printf("%d ",dis[i]);
return 0;
}
例题：
P3371 【模板】单源最短路径（弱化版）
P4779 【模板】单源最短路径（标准版）
P3385 【模板】负环
P1576 最小花费
P1629 邮递员送信
先用正图做一遍1为起点 Dijkstra ,再建反图跑n遍以1为终点的 Dijkstra
反图：把所有 \(u \to v\) 的边改成 \(v \to u\)
P6175 无向图的最小环问题
本题可以用用 Floyd 算法
首先这一定是一个简单环。
想一想这个环是怎么构成的。
在枚举 \(k_{i}\) 的时候，我们已经得到了前 \(k-1\) 个点的最短路径
f[x][y] 和 \((k,x), (k,y)\)共同构成了环。
所以连接 $ x \to y \to k \to x $ ，我们就得到了一个经过 \(x , y , k\) 的最小环
在 Floyd 的过程中枚举 k，计算这个和的最小值即可。
#include
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int inf=1e13;
const int N=1e2+7;
ll dis[N][N],mp[N][N];
ll ans=inf;
int n,m;
signed main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
if(i!=j)
dis[i][j]=mp[i][j]=inf; // 初始化
for(int i=1,u,v,w;i<=m;++i) {
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=min(dis[u][v],w);
mp[u][v]=mp[v][u]=min(mp[u][v],w); // 判断重边
}
for(int k=1;k<=n;++k) { // 枚举中转点
for(int i=1;i P1144 最短路计数
将每条边的边权设为1，加一个计数装置进去，具体细节看代码
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=100003;
const int N=1e6+7;
vector edge[N];
int dis[N],ans[N];
bool inque[N];
int n,m;
inline void SPFA() {
queue q;
memset(dis,inf,sizeof(dis));
dis[1]=0;
inque[1]=true;
ans[1]=1;
q.push(1);
while(!q.empty()) {
int u=q.front();
q.pop();
inque[u]=false; // 取出队首的点
for(int i=0,v;idis[u]+1) {
dis[v]=dis[u]+1;
ans[v]=ans[u]; // 更新答案
if(!inque[v])
q.push(v),inque[v]=true; // 入队
}
else if(dis[v]==dis[u]+1)
ans[v]=(ans[u]+ans[v])%mod; // 更新答案
}
}
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i) {
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u); // 建边
}
SPFA();
for(int i=1;i<=n;++i)
printf("%d\n",ans[i]);
return 0;
}
P1744 采购特价商品
简单的最短路，边权设置为它们的欧几里得距离