算法设计与分析 课件 10.3.3-综合应用-最短路径问题-贝尔曼福特算法

信息工程大学算法设计与分析综合应用—最短路径问题-贝尔曼·福特算法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版当图中存在负权边时，迪杰斯特拉算法无法正确求解单源最短路径问题。这种情况下，该如何求解呢？理查德·贝尔曼（RichardBellman）和莱斯特·福特共同提出了Bellman-Ford算法。

该算法可以求解有负权边的单源最短路径问题，也可以判断图中是否存在负环。

边(u,v)的松弛过程：Relax(u,v,w){if(d[v]>d[u]+w(u,v)){d[v]=d[u]+w(u,v);pre[v]=u;}}d[v]：记录源点s到v的最短路径估计w(u,v)：记录点u到点v的边的权值pre[v]：记录点v的前驱uvsBellman-Ford算法通过边的松弛操作得到单源最短路径。Bellman-Ford算法过程：1.对所有边进行(|V|-1)

轮松弛操作，得到源点到所有点的最短路径长度；2.再进行1轮松弛操作，如果发现某些点的最短路径长度仍有更新，则说明图中存在负环。

初始化点dpreA0-1B∞-1C∞-1D∞-1E∞-11.初始化，设源点为A。初始化d数组。初始化pre数组。

初始化第一轮点dpredpreA0-10-1B∞-1-1AC∞-12BD∞-11BE∞-11B2.对所有边进行第一轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。

初始化第一轮第二轮点dpredpredpreA0-10-10-1B∞-1-1A-1AC∞-12B2BD∞-11B-2EE∞-11B1B3.对所有边进行第二轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。

初始化第一轮第二轮第三轮第四轮第五轮点dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1B4.对所有边进行第三~五轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。/*贝尔曼•福特算法求解单源最短路径*/voidBellman-Ford(G,w,s){/*G表示有向网，w表示邻接矩阵，s表示源点*//*1.初始化*/d[s]=0;pre[s]=-1;foreachv∈V-{s}{d[v]=+∞;pre[v]=-1;}

/*2.松弛步骤*/fori=1to|V|-1foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)){ d[v]=d[u]+w(u,v); pre[v]=u;}

/*3.检查是否存在负值环*/foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)) printf(“存在负值环”);}时间复杂度：O(VE)

定理：如果图G=(V,E)不包含负环，执行Bellman-Ford算法后，d[v]即是源点s到点v的最短路径距离。证明：假设v是G中的任一结点，从源点s到v、且边数最少的最短路径为p，如图10-10所示：

证明：假设v是G中的任一结点，从源点v0到vk、长度最短且边数最少的最短路径为p，如下图所示：

由于p是最短路径，有d[vi]=d[vi-1]+w(vi-1,vi)。

第一轮遍历后，有d[v1]=d[v0]+w(v0,v1)；

第二轮遍历后，有d[v2]=d[v1]+w(v1,v2)；

……

第k轮遍历后，有d[v]=d[vk]=d[vk-1]+w(vk-1,vk)。

由于图G没有负值环存在，路径p是一条简单路径（边数最少），因此，路径p最多有(|V|-1)条边，Bellman-Ford算法经过(|V|-1)轮遍历后，可以得到每个点的单源最短路径。

推论：如果在(|V|-1)轮遍历后，存在某个点的最短路径距离仍然有变化，那么G中存在负值环。

如下图所示，经过(|V|-1)轮遍历，可得从源点到v1、v2、…、vk的当前最短路径距离；

继续进行第|V|轮遍历时，假定从vk到v2存在一条边，此时d[v2]=min{d[v2],d[vk]+w(vk,v2)}，若d[v2]有更新，说明从源点s(v0)->v1->v2->…->vk->v2是比s(v0)->v1->v2更短的一条路径，即v2->…->vk->v2构成一个负值环。因此，推论成立。负环思考：什么情况发生松弛操作？只有d[u]更新后，从u发出的点才可能进行松弛操作。

初始化第一轮第二轮第三轮第四轮第五轮点dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1BBellman-Ford算法的优化1.首先对从源点发出的边进行松弛操作；2.找到d[u]降低的点u，继续对从点u发出的边进行松弛操作；3.重复步骤2，直到所有点的最短路径长度d[i]都不再改变。SPFA(ShortestPathFasterAlgorithm)while(队列不为空){取出队列中结点；松弛它发出的边；把最短路径长度有更新的点加入队列；}队列d[A]d[B]d[C]d[D]d[E]A0∞∞∞∞B、C0-14∞∞C、D、E0-1211D、E0-1211E0-1211D0-12-210-12-21S