首页 > 笔记 > 图的最短路径算法

图的最短路径算法

接着坑图论。。。

好久以前就想总结一下了。。。各种最短路233

floyed、dijkstra、bellman、spfa。。。

前提知识

单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。

最短路径的最优子结构性质

该性质描述为:如果P(i,j)={Vi….Vk..Vs…Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设P(i,j)={Vi….Vk..Vs…Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

1、floyed

Floyd算法:
(1)初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应元素为权值;否则为无穷
(2)逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值
(3)所有顶点试探完毕,算法结束

伪代码

c++核心代码

这个算法就是背背代码。。。优点是简单,缺点就是效率太低O(n3)。。。

下面是个板子。。。

2、dijkstra

描述

求单源、无负权的最短路。时效性较好,时间复杂度为O(VV+E),可以用优先队列进行优化,优化后时间复杂度变为0(vlgn)。

源点可达的话,O(VlgV+ElgV)=>O(E*lgV)。

当是稀疏图的情况时,此时E=VV/lgV,所以算法的时间复杂度可为O(V^2) 。可以用优先队列进行优化,优化后时间复杂度变为0(vlgn)。

流程

由前提知识可知,如果存在一条从i到j的最短路径(Vi…..Vk,Vj),Vk是Vj前面的一顶点。那么(Vi…Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路,

假设存在G=<V,E>,源顶点为V0,U={V0},dist[i]记录V0到i的最短距离,path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.直到U=V,停止。

下面是流程图

经典的流程图

images

动态流程图

详细流程图

(库存的图已经用光了)

(图片均来自于网络)

dij可以用堆优化。。。就是当把点放入最短路径集合的时候,把边压入一个小根堆,更新的时候直接弹出来。。。

伪代码

中文版

算导版

实现

先给一个非常详细的,用邻接矩阵实现。。。(效率很低)

来自网络

结果

images

下面是我写的一个堆优化dij,用的邻接表储存(理论最快)

例题luogu1139(上面就是题解)

3、Bellman-Ford

简介

Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。

这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。

求单源最短路,可以判断有无负权回路(若有,则不存在最短路),时效性较好,时间复杂度O(VE)。

适用条件&范围:

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

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

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

差分约束系统;

Bellman-Ford算法的流程如下:

给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为, Distant[s]为0;

以下操作循环执行至多n-1次,n为顶点数:

对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;

若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;

为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

流程

Bellman-Ford算法可以大致分为三个部分

第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。

第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。

第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:

d(v) > d (u) + w(u,v)

则返回false,表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。

images

images

代码

结果

images

images

这个算法意义不大。。效率太低,根本没法用。但是它的优化spfa还是可以一看的。。。

4、spfa

spfa就是bellman的队列优化。名字叫Shortest Path Faster Algorithm,一听就很有逼格。但是实现非常简单。

简介

SPFA算法可以用于存在负数边权的图,这与dijkstra算法是不同的。

与Dijkstra算法与Bellman-ford算法都不同,SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时
间有很大的差别。

在最好情形下,每一个节点都只入队一次,则算法实际上变为广度优先遍历,其时间复杂度仅为O(E)。另一方
面,存在这样的例子,使得每一个节点都被入队(V-1)次,此时算法退化为Bellman-ford算法,其时间复杂度为
O(VE)。

SPFA算法在负边权图上可以完全取代Bellman-ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。

流程

几乎所有的最短路算法其步骤都可以分为两步

1.初始化

2.松弛操作

初始化: d数组全部赋值为INF(无穷大);p数组全部赋值为s(即源点),或者赋值为-1,表示还没有知道前驱

然后d[s]=0;  表示源点不用求最短路径,或者说最短路就是0。将源点入队;

(另外记住在整个算法中有顶点入队了要记得标记vis数组,有顶点出队了记得消除那个标记)

队列+松弛操作

读取队头顶点u,并将队头顶点u出队(记得消除标记);将与点u相连的所有点v进行松弛操作,如果能更新估计值(即令d[v]变小),那么就更新,另外,如果点v没有在队列中,那么要将点v入队(记得标记),如果已经在队列中了,那么就不用入队

以此循环,直到队空为止就完成了单源最短路的求解

古老的流程图

首先建立起始点a到其余各点的最短路径表格

images

首先源点a入队,当队列非空时:
1、队首元素(a)出队,对以a为起始点的所有边的终点依次进行松弛操作(此处有b,c,d三个点),此时路径表格状态为:

在松弛时三个点的最短路径估值变小了,而这些点队列中都没有出现,这些点需要入队,此时,队列中新入队了三个结点b,c,d

队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e点),此时路径表格状态为:

images
在最短路径表中,e的最短路径估值也变小了,e在队列中不存在,因此e也要入队,此时队列中的元素为c,d,e

队首元素c点出队,对以c为起始点的所有边的终点依次进行松弛操作(此处有e,f两个点),此时路径表格状态为:

images

在最短路径表中,e,f的最短路径估值变小了,e在队列中存在,f不存在。因此e不用入队了,f要入队,此时队列中的元素为d,e,f

队首元素d点出队,对以d为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

在最短路径表中,g的最短路径估值没有变小(松弛不成功),没有新结点入队,队列中元素为f,g
队首元素f点出队,对以f为起始点的所有边的终点依次进行松弛操作(此处有d,e,g三个点),此时路径表格状态为:

images

在最短路径表中,e,g的最短路径估值又变小,队列中无e点,e入队,队列中存在g这个点,g不用入队,此时队列中元素为g,e
队首元素g点出队,对以g为起始点的所有边的终点依次进行松弛操作(此处只有b点),此时路径表格状态为:

images
在最短路径表中,b的最短路径估值又变小,队列中无b点,b入队,此时队列中元素为e,b
队首元素e点出队,对以e为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

images

在最短路径表中,g的最短路径估值没变化(松弛不成功),此时队列中元素为b
队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e这个点),此时路径表格状态为:

images
在最短路径表中,e的最短路径估值没变化(松弛不成功),此时队列为空了
最终a到g的最短路径为14

代码实现

伪代码

c++邻接表实现

例题luogu1139(上面就是题解X2)


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×