文章目录
- 从Bellman-Ford开始
- 核心思想
- 模拟算法执行过程
- 时间复杂度
- 模板
- spfa
- spfa优化的思想
- 模板
从Bellman-Ford开始
- 对于所有边权都大于等于0的图,任意两个顶点之间的最短路,显然不会经过重复的顶点或者边。也就是说任意一条最短路经过的定点数不会超过n个,边不会超过n-1条边
- 而对于有边权为负的图,有可能图中会存在负环,此时途径负环的最短路没有意义。
核心思想
B
e
l
l
m
a
n
−
F
o
r
d
Bellman-Ford
Bellman−Ford的核心思想是松弛操作,即对于边
(
u
,
v
)
(u,v)
(u,v),用
d
i
s
t
(
u
)
和
l
(
u
,
v
)
dist(u)和l(u,v)
dist(u)和l(u,v)的和尝试更新
d
i
s
t
(
v
)
:
dist(v):
dist(v):
d
i
s
t
(
v
)
=
m
i
n
(
d
i
s
t
(
v
)
,
d
i
s
t
(
u
)
+
l
(
u
,
v
)
)
dist(v)=min(dist(v),dist(u)+l(u,v))
dist(v)=min(dist(v),dist(u)+l(u,v))
B e l l m a n − F o r d Bellman-Ford Bellman−Ford所做的,就是不断尝试对图上每一条边进行松弛操作。
我们会进行多次迭代,每进行一次迭代,就对图上所有的边都尝试进行一次松弛操作,当一次迭代中没有点的 d i s t dist dist发生改变时,算法停止。
模拟算法执行过程
在每次迭代中,遍历所有边,尝试进行松弛操作
因为这里 B B B还是正无穷,还没找到从起点到 B B B的最短路,这样通过当前的 B B B更新其他点是没有意义(这也是后面 s p f a spfa spfa优化的关键)
至此第一轮迭代完成,下面是第二轮迭代
第四次迭代已经什么都更新不了了
时间复杂度
在最短路存在的情况下(图中不存在负环),由于一次迭代会使最短路的边数至少加 1 1 1,而 S S S到每个顶点的最短路经过的边数最多为 n − 1 n-1 n−1,因此整个算法最多会进行 n − 1 n-1 n−1轮迭代,每一轮迭代的复杂度为 O ( m ) O(m) O(m)(每条边枚举到一次),所以总的时间复杂度为 O ( n m ) O(nm) O(nm)
- 当从 S S S点出发能到达一个负环时,就会进行n论以上的迭代
模板
int n, m; // n表示点数,m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边,a表示出点,b表示入点,w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
spfa
spfa优化的思想
s
p
f
a
spfa
spfa是通过队列来优化
b
e
l
l
m
a
n
−
f
o
r
d
bellman-ford
bellman−ford算法
在每一次迭代时,只有在上一次迭代中被更新了距离的点,才有可能去更新其他节点。因此,在每一次迭代时,我们将更新过距离的顶点加入一个队列(如果顶点已经在队列里则不加),在下一次迭代时,只需要遍历队列中的顶点连出去的边即可。
- 在实际实现过程中我们不关心具体是那一次迭代。
模板
vector<vector<pii>>g(n+1);
rep(i,1,m){
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
vector<vector<int>>inq(n+1);
vector<vector<int>>d(n+1,0x3f3f3f3f);
queue<int>q;
d[1]=0;
inq[1]=1;
q.push(1);
//跑一遍最短路
while(q.size()){
auto t=q.front();
q.pop();
int u=t.x,cnt=t.y;
inq[u]=0;
for(auto it:g[u]){
int v=it.x,w=it.y;
//松弛操作,或者其他变形具体问题具体分析
if(满足松弛){
//更新
if(!inq[v]){
inq[v]=1;
q.push(v);
}
}
}
}