Bellman-ford求最短路问题

​ 今天来学习一下Bellman-ford求最短路，Bellman-ford是一个解决负权值的最短路问题的算法。不过时间复杂度很高(O(nm))

​ Bellman-ford的步骤为：

​ 1.存图

​ 2.进行初始化为无穷大,并将dist[初始] = 0 ；

​ 3.循环k次(k是最多经过几条边，没有特殊要求就是n-1了)

​ 4.在循环中使用新的数组来取代dist[^这个的原因是，如果使用dist，容易一次性更新多条边 ]

​ 5.遍历每一个点，如果点不是无穷大，那就遍历这个点的相邻线路，并且如果有最短路就更新相邻线路

​ 6.输出答案

接下来就是代码辣~

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
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int N = 550 ; 
struct Dim{
	int v ;
	int w ; 
};
vector<Dim>st[N]  ; 
const int inf = 0x3f3f3f3f ; 
void solve(){
	int n , m , k ; cin >> n >> m >> k ; 
	for(int i = 1 ; i<= m ; i++){
		int x , y , c ; cin >> x >> y >> c ; 
		st[x].push_back({y,c}) ; //存图 
	}
	vector<int>dist(n+1 , inf) ; //因为赋值麻烦，所以考虑动态 
	dist[1] = 0 ;
	for(int i = 1 ; i<= k ; i++){
		vector<int>backup = dist ; //这东西可以直接等于赋值 
			
		for(int u = 1 ;u <= n ; u++){
			if(backup[u] == inf)continue ; //如果不跳过
			for(const auto &y : st[u]){
				if(dist[y.v] > backup[u]+y.w){
					dist[y.v] = backup[u]	+y.w;
				}
			} 
		}
	}
	if (dist[n] == inf) {
        cout << "impossible" << endl;
    } else {
        cout << dist[n] << endl;
    } 
}
int main(){

	ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t = 1;
    // cin >> t;
    while (t--) {
    	
        solve();
    }
    
    return 0;
}

感谢观看，如果对你有帮助，就点个赞吧！