Bellman-Ford算法
求最短路的
这个算法基于一个叫做“松弛”的操作
松弛会试图往最短路中加边来缩短最短路
对于这样一个图
1到3的最短路显然是1→2→3而不是1→3绕远路就是最短的捷径
我们所进行的松弛操作就是这样的
松弛时枚举每一条边，并判断先走最短路到达这条边的u点，再经过这条边到达v点，能否使到v点的最短路缩小
若可以，就将到v点的最短路更新
显然，只用一次松弛不能够得到完整的最短路，所以要进行多次松弛
经过一大堆乱七八糟的玄学证明，我们知道只需要进行n-1次松弛即可
所以，当n=1时，我们只要进行0次松弛即可
n=2时，1次即可
n=3，3次即可
n=2147483647，2147483646即可
不行这个数太大了
实际上我们发现，n-1是最大次数
实际上有效松弛有可能没有这么多
所以我们判断如果这次松弛没有让最短路发生变化，就直接结束算法
对于负权环，由于正常情况下最多进行n-1次有效松弛，如果在n-1次全部完成后还可以松弛，就可以说明这里面有负权环了
代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Edge
{
int u,v,w,nxt;
}e[10];
int h[10],cnt;
int dis[10];
int bak[10];
void add(int u,int v,int w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
for(int i=1;i<=n;i++)
dis[i]=0x3f;
dis[1]=0;
for(int k=1;k<=n-1;k++)
{
for(int i=1;i<=n;i++)
bak[i]=dis[i];
for(int i=1;i<=m;i++)
if(dis[e[i].v]>dis[e[i].u]+e[i].w)
dis[e[i].v]=dis[e[i].u]+e[i].w;
int check=0;
for(int i=1;i<=n;i++)
if(bak[i]!=dis[i])
{
check=1;
break;
}
if(!check)
break;
}
int flag=0;
for(int i=1;i<=m;i++)
if(dis[e[i].v]>dis[e[i].u]+e[i].w)
flag=1;
if(flag==1)
cout << "无最短路" << endl;
else
{
for(int i=1;i<=n;i++)
cout << dis[i] << ' ';
}
return 0;
}
但是我们回头看看这个代码
松弛时枚举每一条边
每一条
根据我的经验，我怀疑这里面有可能有许多没用的松弛
实际上我们可以通过一大堆乱七八糟的玄学证明，松弛只有可能令一部分点的最短路缩小
这一部分点就是松弛时所加入的那条边的v点所连着的点
于是我们就接触到了另一个算法，另一个在Bellman-Ford算法基础上的最短路算法——
Shortest Path Faster Algorithm
它利用队列，每次取出队首，枚举队首所有的边进行松弛
并将那些松弛成功的边的v点入队
以达到避免无效松弛的效果
代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Edge
{
int u,v,w,nxt=-1;
}e[10];
int h[10],cnt;
int dis[10];
int bak[10];
void add(int u,int v,int w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt;
}
queue<int> q;
int bk[10];
int main()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
for(int i=1;i<=n;i++)
dis[i]=999999;
dis[1]=0;
for(int i=1;i<=n;i++)
bk[i]=0;
q.push(1);
bk[1]=1;
while(!q.empty())
{
int k=h[q.front()];
while(k!=-1)
{
if(dis[e[k].v]>dis[e[k].u]+e[k].w)
{
dis[e[k].v]=dis[e[k].u]+e[k].w;
if(bk[e[k].v]==0)
{
q.push(e[k].v);
bk[e[k].v]=1;
}
}
k=e[k].nxt;
}
bk[q.front()]=0;
q.pop();
}
for(int i=1;i<=n;i++)
cout << dis[i] << ' ';
return 0;
}