图论：最短路-Bellman-Ford

我们之前介绍了一种，（最常用的）SPFA算法，SPFA算法是对Bellman-Ford算法的队列优化，用队列替代了Bellman-Ford中的循环检查部分

然后这里我们介绍Bellman-Ford算法是为了介绍其对负权环的判定部分，以及这部分在SPFA的体现

首先是建图部分，邻接链表，其实对于Bellman-Ford算法来说，边表足矣

int g[maxn],d[maxn];
struct Edge{int u,t,w,next;}e[maxm];
void addedge(int x,int y,int z)
{
    cnt++;e[cnt].u=x;e[cnt].t=y;e[cnt].w=z;
    e[cnt].next=g[x];g[x]=cnt;
}

原本青涩的邻接表变成了现在的样子，自从看了黄学长的代码风格，压行写可能更加舒适一些。。

这里我们对于每一条边，记录其起始节点，和边表结构统一

然后，是算法的核心部分：

    for(int i=1;i<=n;i++) d[i]=INF;
    d[s]=0;
    for(int k=0;k<n-1;k++)
    for(int i=1;i<=m;i++)
    {
        int x=e[i].u,y=e[i].t;
        if(d[x]<INF) d[y]=min(d[y],d[x]+e[i].w);
    }

其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成

然后是对于负权环的判断部分：

    bool flag=1;
    for(int i=1;i<=m;i++)  
    if(d[e[i].t]>d[e[i].u]+e[i].w){flag = 0;break;}  
    return flag;

对于每一条边进行检查，如果发现还能松弛，就存在负权环

最后给出完整实现，请注意如果每一条边的长度过大，在INF处一定不要越界，还有无向图的二倍边一定要记住

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=10005;
 5 const int maxm=500005;
 6 const int INF=0x7fffffff; 
 7 int s,n,m,cnt;
 8 int g[maxn],d[maxn];
 9 struct Edge{int u,t,w,next;}e[maxm];
10 void addedge(int x,int y,int z)
11 {
12     cnt++;e[cnt].u=x;e[cnt].t=y;e[cnt].w=z;
13     e[cnt].next=g[x];g[x]=cnt;
14 }
15 bool bellman_ford(int s)
16 {
17     for(int i=1;i<=n;i++) d[i]=INF;
18     d[s]=0;
19     for(int k=0;k<n-1;k++)
20     for(int i=1;i<=m;i++)
21     {
22         int x=e[i].u,y=e[i].t;
23         if(d[x]<INF) d[y]=min(d[y],d[x]+e[i].w);
24     }
25     bool flag=1;
26     for(int i=1;i<=m;i++)  
27     if(d[e[i].t]>d[e[i].u]+e[i].w){flag = 0;break;}  
28     return flag;  
29 }
30 int main()
31 {
32     scanf("%d%d%d",&n,&m,&s);
33     int x,y,z;
34     for(int i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);}
35     bellman_ford(s);
36     for(int i=1;i<=n;i++) {printf("%d ",d[i]);}
37     return 0;
38 }

在SPFA中开一个数组记录每一个点的入队次数，如果一个点重复入队了n次，说明存在负权环

总体来说，SPFA算法比Bellman-Ford更加优越，稠密图情况二者的效率是差不多的

稀疏图来说，SPFA可能要快于Dijkstra并且，网格图可以把SPFA卡回原型