资源描述：
《1求含有负权边的图的单源最短路径——bellmanford算法与spfa算法综合分析(上)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、求含有负权边的图的单源最短路径一一BellmanFord算法与SPFA算法综合分析对于不含负权边的图求单源最短路径，Dijkstra算法是最高效的。但是在含负权边的图中，Dijkstra很可能得不到正确的结果，因为Dijkstra每次选的是当前能连到的边中权值最小的，在正权图中这种贪心是对的，但是在负权图中就不是这样了。比如1——>2权值为5,1——>3权值为6,3——>2权值为・2,求1到2的最短路径时，Dijkstra就会选择权为5的1一一>2,但实际上1一一>3一一>2才是最优的结果。Bellman-Ford与SPFA都是解决这一问
2、题的算法，两者的程序都很简单清晰【其实后者就是前者的一个优化】,所以也比较容易掌握一、Bellman-Ford算法说到Bellman-Ford一定会说到松弛(relaxation)技术，即用d[i]来预计s到i的最短距离。在计算过程屮不断地缩小d[i],直到最后d[i]就是源点s到i的最短距离。至于为什么叫“松弛”，尽管算法导论中给出了一段说明，但我们只需认为这是作者在故弄玄虚即可，松弛就是求单源最短路径的迭代过程,d[i]也可以看为存储当前s到i的最短距离。算法核心代码如下：(针对有向图，Pascal语言)varm:longint;co
3、st:array[1..maxiij1..maxn]oflongint:edge:array[1..maxn^axnj1..2]oflongint;djclosest:array[1..maxn]oflongint:functionbellman_ford(s:longint):boolean;varkjv:longint:beginfori:=ltondobegind[i]:=100000000;closest[i]:=一1:end;d[s]:=0：fori:=lton-1doforj:=1tomdobeginu:二edge[j,1];
4、v:=edge[j32]:ifd[v]>d[u]+cost[u^v]thenbegind[v]:=d[u]+cost[u,v];closest[v]:=u;end;end：fori:=ltomdobeginu:=edge[i,1]:v^edgetij2]:ifd[v]>d[u]+cost[ujv]thenexit(false);end;exit(true);end;阅读上述程序，求解下图各点到点1的最短距离:各点距离：棕色部分：n为图顶点数，m为图边数。Cost[i,j]表示边(i,j)的权Edge存放图的所有边D即上文所述的用于存储当前
5、s到i的最短距离的数组Closest[i]记录s到i的最短路径上i的前趋。最后要求i到s的路径时，只需用递归打印Closest[i].Closest[Closest[i]]^Closest[Closest[Closest[i]]、…、s便可求出整条路径。绿色部分：算法的初始化。对于不为s的所有iev,d[i]初始赋为一个足够大的数来表示无限大【之所以不使用maxlongint而是使用100000000是因为下面要有无限大与实数相加的操作,如果maxlongint就会溢出(201错误)],closest[i]赋为T表示nilod[s]赋为0
6、表示s到s的距离为0。红色部分：算法的迭代求解部分。程序很好理解，就是不断枚举每条边，更新当前找到的最短路径。对于不含负权回路的图，循环n-1次一定能对任意i使d[i]为s到i的最短路径，因为这段过程相当于枚举了s到其他所有点的所有路径。I_s,最短路最多含门-1条边，更新旷1次也就全部更新完毕。蓝色部分：算法的检验部分。上面已经提到，如果是不含负权回路的图，d[i]—定是最短路径，不存在还需要更新的可能性，所以不会执行到exit(false)；至于当exit(false)时一定是存在负权回路的原因，算法导论上有一个比较复杂的证明，但是抛
7、弃严谨的证明的话，理解起来却很容易：当图不含负权冋路时一定不会exit(faIse),逆否命题为当exit(false)吋一定含负权回路。原命题成立，因此逆否命题一定成立。从流程可以看出，Bellman-Ford的时间复杂度为0(EV),对于E接近厂2的稠密图为0(厂3),对于E接近V的稀疏图为0(厂2)。当然，我们可以看到Bellman-Ford做了很多不必要的判断。如果i还没有循环到n-l但已经计算出最小路径时，d边不会再更新，但是循环却还要做到n-1,接下去的运算全部都是没有用的运算。所以我们在循环屮加一个布尔型变量flag,进入外
8、循环时flag设为false,若d有变化则flag改为true。在内循环全部做完后若fl慾还是false则说明算法已经完毕，直接退出算法并返回trueo改进后的算法如下：functionbel
