Bellman-Ford算法

Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛（原文是这么写的，为什么要叫松弛，争议很大），每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个旗帜flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛，所以SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。

<Bellman-Ford算法>

　　Dijkstra算法中不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法。

　　Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。

　　适用条件&范围

　　1.单源最短路径(从源点s到其它所有顶点v);

　　2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

　　3.边权可正可负(如有负权回路输出错误提示);

　　4.差分约束系统;

　　Bellman-Ford算法描述：

　　1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;

　　2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）

　　3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

　　描述性证明：

　　首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。

　　其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。

　　在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。

　　每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）

　　如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。

　　如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

引申：SPFA算法

　　算法简介

　　SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。

　　算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。  

 

 

不过改的spfa算法，注意每个节点进入队列的次数至多为n-1次（一共n个节点），若进入大于等于n次了，则说明图中存在负权回路，此时正好满足题目中时光倒流的要求，另外注意，vector每次用的时候清空。
下面是spfa算法的简单说明：
我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
注意对刚出队列的节点的所有相邻节点都要做松弛操作，不管该节点是否在队列中，不在队列中的松弛点加入到队列即可。

#include <iostream>

#include <fstream>

#include <vector>

#include <queue>

#define INF 999999999

using namespace std;

 

struct E

{

         int v;

         int w;

}edges[6000];

 

vector<E> v[1008];

bool visited[1008];

int dist[1008];

int enterCount[1008];

 

int n,m,w,edgeCount;

 

void addEdge(int e,int s,int t)

{

         edgeCount++;

         edges[edgeCount].v=s;

         edges[edgeCount].w=t;

         v[e].push_back(edges[edgeCount]);

}

 

bool spfa()

{

         int i;

         queue<int> q;

         visited[1]=1;

         dist[1]=0;

         enterCount[1]=1;

         for(i=2;i<=n;i++)

         {

                   visited[i]=0;

                   dist[i]=INF;

                   enterCount[i]=0;

         }

         q.push(1);

         while(!q.empty())

         {

                   int temp=q.front();

                   q.pop();

                   visited[temp]=0;

                   for(i=0;i<v[temp].size();i++)

                   {

                            if(dist[v[temp][i].v]>dist[temp]+v[temp][i].w)

                            {

                dist[v[temp][i].v]=dist[temp]+v[temp][i].w;

                                     if(!visited[v[temp][i].v])                               

                                     {                                            

                                               visited[v[temp][i].v]=1;

                                               enterCount[v[temp][i].v]++;

                                               if(enterCount[v[temp][i].v]>=n)

                                                        return true;

                                               q.push(v[temp][i].v);

                                     }

                            }

                   }

         }

         return false;

        

                                    

}

 

 

int main()

{

         //ifstream cin("1.txt");

         int f,i;

         cin>>f;

         while(f--)

         {

                   cin>>n>>m>>w;

                   edgeCount=0;

                   for(i=1;i<=n;i++)

                            v[i].clear();

                   for(i=0;i<m;i++)

                   {

                            int s,e,t;

                            cin>>s>>e>>t;

                            addEdge(s,e,t);

                            addEdge(e,s,t);

                   }

                   for(i=0;i<w;i++)

                   {

                            int s,e,t;

                            cin>>s>>e>>t;

                            addEdge(s,e,-t);

                   }

                  

                   if(spfa())

                            cout<<"YES"<<endl;

                   else

                            cout<<"NO"<<endl;

         }

         return 0;

}

 

 

#include<iostream>

using namespace std;

const int fMax = 505;

const int eMax = 5205;

const int wMax = 99999;

 

 

 

struct{

    int sta, end, time;

}edge[eMax];

int point_num, edge_num, dict[fMax];

 

 

 

bool bellman_ford()

{

    int i, j;

    for(i = 2; i <= point_num; i ++)

        dict[i] = wMax;

    for(i = 1; i < point_num; i ++)

         {

        bool finish = true;    //  加个全部完成松弛的判断，优化了50多MS。

        for(j = 1; j <= edge_num; j ++)

                   {

            int u = edge[j].sta;

            int v = edge[j].end;

            int w = edge[j].time;

            if(dict[v] > dict[u] + w)

                            {   //  松弛。

                dict[v] = dict[u] + w;

                finish = false;

            }

        }

        if(finish)  break;

    }

    for(i = 1; i <= edge_num; i ++)

         {   //  是否存在负环的判断。

        int u = edge[i].sta;

        int v = edge[i].end;

        int w = edge[i].time;

        if(dict[v] > dict[u] + w)

                           

            return false;

    }

    return true;

}

 

 

 

int main()

{

    int farm;

    scanf("%d", &farm);

    while(farm --)

         {

        int field, path, hole;

        scanf("%d %d %d", &field, &path, &hole);

        int s, e, t, i, k = 0;

        for(i = 1; i <= path; i ++)

                   {

            scanf("%d %d %d", &s, &e, &t);  //  用scanf代替了cin，优化了100多MS。

            k ++;

            edge[k].sta = s;

            edge[k].end = e;

            edge[k].time = t;

            k ++;

            edge[k].sta = e;

            edge[k].end = s;

            edge[k].time = t;

        }

        for(i = 1; i <= hole; i ++)

                   {

            scanf("%d %d %d", &s, &e, &t);

            k ++;

            edge[k].sta = s;

            edge[k].end = e;

            edge[k].time = -t;

        }

        point_num = field;

        edge_num = k;

        if(!bellman_ford()) 

                            printf("YES\n");

        else  printf("NO\n");

    }

    return 0;

}