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

;当图中存在负权边时，迪杰斯特拉算法无法正确求解单源最短路径问题。;理查德·贝尔曼（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;

}

};Bellman-Ford算法过程：

1.对所有边进行(|V|-1)?轮松弛操作，得到源点到所有点的最短路径长度；

2.再进行1轮松弛操作，如果发现某些点的最短路径长度仍有更新，则说明图中存在负环。;;;;;/*贝尔曼?福特算法求解单源最短路径*/

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|-1

foreachedge(u,v)∈E

if(d[v]d[u]+w(u,v)){

d[v]=d[u]+w(u,v);

pre[v]=u;

}?

/*3.检查是否存在负值环*/

foreachedge(u,v)∈E

if(d[v]d[u]+w(u,v))

printf(“存在负值环”);

};定理：如果图G=(V,E)不包含负环，执行Bellman-Ford算法后，d[v]即是源点s到点v的最短路径距离。;推论：如果在(|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发出的点才可能进行松弛操作。;Bellman-Ford算法的优化;while(队列不为空)

{

取出队列中结点；

松弛它发出的边；

把最短路径长度有更新的点加入队列；

};SPFA算法的局限性：

1.无法判断负环，因为一个点可能被入队多次

2.最坏时间复杂度没有改进

3.实际运行效果可能不如Bellman-Ford算法;上述过程是不断发现问题、解决问题的过程！

发现问题比解决问题更重要！