bellman-ford算法理解

从本题谈起再回归到最短路。本题为限制边数的最短路，是这个算法优势领域的题目。为什么它能解决？

  • 最外层每循坏一次，就是各点向外走一条边，内层对边的遍历是对所有边进行松弛操作，每次进行该操作时，需要用到备份数组，目的是防止连锁反应，保证每次每个点到起点的距离只能因为上一轮的更新而更新。

若只是求最短路，则外层循坏n-1次。为什么是n-1？

  1. 假如最短路存在，认为没有负环
    从上面算法理解可以知道，外层n-1次相当于起点已经走过了n-1条边（bfs到n-1层）
    那么从最坏情况考虑，由于已经假设最短路存在，那么其长度应该<=n-1.
  2. 假如最短路不存在
    而如果n-1条边还没有更新到d[n]，即没有找到一条长度<=n-1的路径从1能到n，说明n可能和1不连通或者图中存在负环

bellmanFord也能判负环，但效率没有spfa好，如何判定呢？

  • 外层循坏n-1次后，如果再进行循环松弛操作依然还能发生有效作用（即被成功更新),说明图中存在一条长度为n的路径，而只有n个点，根据抽屉原理，路径上有两个点是同一个点，存在环，而既然我们一直构造的路径是最短路，既然构造出来有环，就说明在没有其他限制的条件下当前从环走可以减小路程，所以判断这个环是负环

代码实现过程tip

  1. 注意初始化d[1]=0;
  2. 用于需要遍历所有边，而每次并不是找点然后拓展这个点得的出边，所以使用结构体储存边是一个刚需

算法最难理解的有两个点

  1. 需要一个备份数组，保留上次的d数组数据，防止其利用上次的d数组
  2. 最终判断时并不是判断是不是等于0x3f3f3f3f,而是比这个数小一点的数，因为bf算法会更新所有边，即使到不了，也可能因为有负环或者负边权而减小，因为bellmanford是无脑遍历所有边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=510;
int d[N],l[N];
typedef long long ll;
struct edge{
	int a,b,c;
}e[20010];

	

int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
	int a,b,c;
	cin>>a>>b>>c;
	e[i]={a,b,c};
	}

		memset(d,0x3f,sizeof d);
		d[1]=0;
	for(int i=0;i<k;i++){
		memcpy(l,d,sizeof d);
		for(int j=1;j<=m;j++){ 
			auto u=e[j];
			d[u.b]=min(d[u.b],l[u.a]+u.c);
		}
	}
	if(d[n]>0x3f3f3f3f/2)cout<<"impossible";
	else cout<<d[n];

	
	
	
	
	
	return 0;

}