bellman_ford算法:
一.什么是贝尔曼-福特算法(英语:Bellman–Ford algorithm):求解单源最短路径问题的一种算法,由理查德·贝尔曼(Richard Bellman) 和莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为Edward F. Moore也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单.
二.其特点和缺陷:
优点:与dijkstra不同的是,它既可以求含有负权边的单源最短路问题,同时可以求有变数限制的单源最短路问题.其中含有松弛操作也很有特色和优势
但缺点就是时间复杂度过高,并且有一定局限(目前就只在有边限制的题目上出现)
三.松弛操作的理解:松弛操作是指对于每个顶点v∈V,都设置一个属性d[v],用来描述从源点s到v的最短路径上权值的上界,称为最短路径估计.用人话讲就在开始第k次更新最短路时,那么我们保留第k次所有1~n的点到1的距离,即为松弛操作
实现的过程需要而外开辟一个数组backup[]来储存第k次操作的dis[1~n]的初值
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 550;
int dist[N],backup[N];
int n,m,k;
bool st[N];
struct node{
int a,b,w;//结构体来存储路径和权值
}d[N*N];
void bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i = 1;i <= k;i ++ )//表示在第i条边内每个点到1的距离
{
memcpy(backup,dist,sizeof dist);//也就是备份第i次开始时的dist[1~n]的值
for(int j = 1;j <= m;j ++ )
{
int a = d[j].a,b = d[j].b,w = d[j].w;
dist[b] = min(dist[b],w + backup[a]);//用备份值来更新,防止在这个循环里面一个点被多余两个串联点更新
}
}
if(dist[n]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
else cout<<dist[n]<<endl;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1;i <= m;i ++ )
cin >> d[i].a >> d[i].b >> d[i].w;
bellman_ford();
return 0;
}