最短路
给定一张
如果起点固定,则称为单源最短路。
如果起点不固定,则称为多源最短路。
这张图必须保证没有长度为负数的环,否则在这个环上一直绕圈,长度会越来越小。
BFS
如果边的长度都是
floyd
假设边用邻接矩阵存储,此时
设
则
设 显然的转移方程
f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);
用三重循环把转移完整地写出来:
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
f[k][i][j]=min(f[k-1][i][k]+f[k-1][k][j]);
}
}
}
2
3
4
5
6
7
8
9
10
事实上第一维对转移没有影响
因为无论是从
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
f[i][j]=min(f[i][k]+f[k][j]);
}
}
}
2
3
4
5
6
7
8
9
10
注意这里的
当
若
弗洛伊德得到的最短路是全源最短路,任意两个点之间的距离都能得到
最小环
假设图是简单图(没有重边和自环)
最小环一定是一个简单环(不存在环套环)
设环中编号最大的点是
当得到
传递闭包
当某种关系具有传递性时(必须某两个点是否联通),可以用
f[i][j]|=f[i][k]&f[k][j];
进一步可以用 bitset 优化到
bellman-ford
该算法适用于求单源最短路,即从固定起点出发到其他点的最短路
设一个数组
如果存在一条 dis[t]=min(dis[t],dis[u]+v)
来松弛
因为最短路最多经过
可以设计一个算法,每次用所有边进行依次松弛,最终一定能得到最短路。
for(int i=1;i<n;++i)//松弛次数
{
for(int u=1;u<=n;++u)
{
for(auto [t,v]:eg[u])//u->t,长度为v的边。
{
dis[t]=min(dis[t],dis[u]+v);
}
}
}
2
3
4
5
6
7
8
9
10
也可以进行
每轮松弛访问所有边一次,总时间复杂度
spfa
第一次松弛,只有起点的距离是已知的,说明只有从起点出发的边是有用的。
第二次松弛,只有起点周围一圈的距离是已知的,说明只有这一圈点出发的边是有用的。
……
第
开一个队列,将所有
while(!q.empty())
{
int now=q.front();
q.pop();
//vis[now] 表示 now 是否在队列里,防止一个点占好几个位置
vis[now]=0;//出队列
for(auto [t,v]:eg[now])
{
if(dis[t]>dis[now]+v)
{
dis[t]=dis[now]+v;
if(!vis[t]) q.push(t);//如果发生了改变,进队列
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
可以给每个点记录一下
它的最坏复杂度也是
不推荐在平常情况下写这个算法,除非是判断负环或者边有负数。
dijkstra
当图中的边长度没有负数时求单源最短路:
那么有一个神奇的事情,如果一个点的
举例:
如果没有边的长度是负数,那么此时
如果有边的长度是负数,那么则不一定,有可能
建立在没有负数长度边的前提下,我们可以每次直接取出还没取过的
它的本质可以说是贪心算法。
要取最小的,所以把队列改成堆(优先队列),存两个参数,第一个是当前点的
while(!q.empty())
{
int now=q.top()[1];//[0] 是长度, [1] 是编号
q.pop();
if(vis[now]) continue;//如果这个点被选过就跳过
vis[now]=1;
for(auto [t,v]:eg[now])
{
if(dis[t]>dis[now]+v)
{
dis[t]=dis[now]+v;
q.push(pr{dis[t],t});//如果成功松弛,将松弛后的点加入优先队列。
//因为优先队列中要存dis[t],而且每次松弛后dis[t] 长度不同,所以相同的点也必须都加进去,而不是像spfa只存一个。
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度:
最多
分层图
在无负长度边情况下,求最短路径,且可以令任意
将图视作一共
即如果本来存在
可以从
层数增加是不可逆的,符合了建模的想法,最后
可以直接将状态设计成