Bellman-Ford及其队列优化

说白了这玩意可以处理负边权,和 Dijkstra 看起来一样但却有着微妙的不同..

未优化前

优化后

一些分析

可以看的出该算法是以把边扔进去试一试为主,Dijkstra 算法的找最小值那一步体现了它基于贪心,而Bellman-Ford 算法则是从边的点出发,企图通过给定边(u,v)来达到 v 点或者说看能不能缩短源点 s 到 v 的距离(一开始是 inf )。 第一轮把所有边扔进去试,松弛结束后 dis[ ] 数组更新,开始进行第二轮松弛,重新把所有边扔进去算(注意此时会存在冗杂的现象,因为一些点的值已成为确定值)。

事实上可以发现第一次松弛时 dis[ ] 数组只有与源点相邻的点才会更新,而后可以发现第 k 次松弛代表着用 k 条线路可以达到的最小值(即表现为对 dis[ ] 数组的更新)即使出现负边权,设这条蛋疼的边为 x(u,v),则迟早会对 v 进行真正的松弛,(其实第一次把边代进去会缩小 dis[ v ] 的值,就算 dis[ u ] 是 inf , 
dis[ v ] > x(u,v)+ dis[ u ] )我指的真正的松弛是当 dis[ u ] 不为 inf 时,dis[ v ] 再次被更新,然后。。看起来负权边对后续就没什么影响了。。(大概)

而当算了n-1轮后结束,则能给出最短路径。若还能再松弛,则说明出现负权回路。因为若进行了n轮说明了居然存在一条路在通过n个点时的权值比以往的还小,这就说明存在一条路它的值可能为 -100000 之类的,这时就要报错了,这也是Bellman-Ford 的特征:可以处理负权环路。

优化分析

Bellman-Ford算法在每一次实施松弛操作时,就会有一些顶点已经求得最短路径,此后这些顶点的最短路径的估计值就会一直保持不变,不再受后续松弛操作的影响,但是每次还要判断是否需要松弛,这里浪费了大量的时间.

思想:每次选取队首顶点u,对顶点u的所有出边进行松弛操作,例如有一条u->v的边,如果通过u->v的这条边使得源点到顶点v的最短路径变得更短,也即(dis[u] + e[u][v] < dis[v]),并且顶点v不在当前的队列(并用借助一个数组标记顶点是否已经在队列之中),则将顶点v放置队尾. 对顶点u的所有出边松弛完毕之后,就将顶点u出队,接下来不断从队列中取出新的队首顶点反复上面操作直到队列为空结束. 
队列优化的Bellman-Ford的关键之处: 只有那些在前一遍松弛中改变了最短路径估计值的点,才可能引起它们邻接点最短路径估计值发生改变. 因此用一个队列保存被成成功松弛的顶点,之后只对队列中的点进行处理,这就降低了算法的时间复杂度


来自CSDN的说明

说白了就是如果入队成功则代表这个点有资格作为中转站,如果松弛失败了则对它的后续操作是没有意义的,并且可以看到每次把边带进去时是代头指针指向的点的邻边,不会一开始就浪费资源去搞其他边。(大概是这个样子)

(逃

 

发布者

我乃堂堂SCUT的一条咸鱼!

发表评论

电子邮件地址不会被公开。 必填项已用*标注