SPF(Dijkstra)算法完美教程
独家制作SPF算法深度揭秘,一看就懂!!
摘要:
SPF(shortest path first)算法也叫Dijkstra(迪杰斯特拉)算法,由上个世纪的计算机科学家狄克斯特拉提出,是离散数学中一种经典高效的网络(连通图)最短路径寻路算法.指定一个源点,求出到其余各个顶点的最短路径,也叫”单源最短路径”.
应用场景:
地图导航以及网络路由等.
主要特点:
单个节点拥有上帝视角;以源点为中心向外层层扩展直到终点.
输入:
已知有限个节点和唯一的源点;已知每一条边的权重并且是正数.
循环周期:
先确认距离最短的下一跳,再更新下一跳的邻居.
输出:
得到从源点到剩下所有节点的最短路径信息.
案例拓扑图:
以上面这张复杂的图为例.SPF算法本来是解决有向图的,但因为有向图自然包括了无向图,所以我选择了这张更具代表性的地图.
然后核心问题就是分别求出v0到v1~v8的最短路径.
和Floyd-Warshall算法一样,用二维数组MAP[][]来存放上图每条链路的开销(每条边的权),然后计算机从这个数据库中算出一棵棵SPF树:
MAP | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 5 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
v1 | / | 0 | 3 | 7 | 5 | ∞ | ∞ | ∞ | ∞ |
v2 | / | / | 0 | ∞ | 1 | 7 | ∞ | ∞ | ∞ |
v3 | / | / | / | 0 | 2 | ∞ | 3 | ∞ | ∞ |
v4 | / | / | / | / | 0 | 3 | 6 | 9 | ∞ |
v5 | / | / | / | / | / | 0 | ∞ | 5 | ∞ |
v6 | / | / | / | / | / | / | 0 | ∞ | 7 |
v7 | / | / | / | / | / | / | / | 0 | 4 |
v8 | / | / | / | / | / | / | / | / | 0 |
注意,这是一张静态表,也就是这张表中数据是不会变化的,为了和后面要用到的动态数组区分开来.
因为是无向图(也可理解为双向图),所以表格沿主对角线两边对称,下三角形就用”/“代表省略.
每个单元格的行和列坐标对应了上图中哪两个节点之间的路径开销,这里认为节点到自己的路径开销为0.剩下不直接相连的两个节点之间都用”∞”表示无穷大.以上就是和Floyd-Warshall表格的不同之处.这张表也就是数字化的拓扑图,便于程序读取其中数据.
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 5 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
然后我们需要一个动态一维数组min[].它的初始状态就是MAP中第二行(v0那一行),末状态就是整个算法要得到的结果:v0到其余所有节点的最短路径开销总值.
初状态:
这张表的工作模式可以类比网络世界里各种IP协议中司空见贯的”cost字段”,言下之意即是:先保留一个非常”劣”缺省值,一遇到更优的数值就更新这个字段,直到收敛成最优为止.这张表非常重要,之后会一直用到它.其中9个字段中提前收敛到最优值(不会在减小)的已经确定的最短路径我们称之为”真”(在表中不妨标记为红色数字),正好对应了C语言中bool变量的”true”.这里体现了设置缺省值的重要思想,通常把∞的大小设置成99999.
具体详解:
做完前期准备,正式进入SPF算法每一步的详解.
我将以上图为例叙述一遍完整的计算过程,亲爱的读者们若是看懵逼了请别慌,后面会有一个完整的总结帮助你理解!
首先min中v0列恒为0,所以永”真”.然后非无穷的”1”和”5”是v0的全部邻居,其中取最小的”1”就是v0到v1的最短路径,v1列”真”.原因显而易见,如果有其他路径到达v1,必然要经过其他的邻居,那些路径(这里只有走v2的那条)都比”5”大,所以都排除.
此时v2列还无法确认是真,因为有可能从更近的v1出去再到达v2的某条路径更短.所以我接下来一个动作是从v1发散到v1所有的邻居并更新min表.
CPU查看MAP时发现v1可到达v2,v3和v4.v0就不用去了,第一是环路,第二v0列已经是真,无法再刷新该字段.由此v0通过v1到达v2,v3和v4的开销为3 1,7 1,5 1.然后刷新min表:
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 8 | 6 | ∞ | ∞ | ∞ | ∞ |
到此为止,SPF算法已经完成了第一个循环周期,即开篇所说的:先确认距离最短的下一跳(即确认真值v1),再更新下一跳的邻居(发散v1并更新min表).专业术语中周期后半部分的”发散”被称为”松弛”,但个人觉得前者更通俗易懂,所以下文我都用”发散”来表达这个过程.接下来进入第二个周期:
此时最小的v2列为真!!(我当时就在这个点上纠结了一个小时…)因!为!通过前两个已经为真的v0和v1发散出去的所!有!路径(止于邻居)都赫然写在min表中(4,8,6),也就是说其他到达v2的路径长度至少也要大于6.大家如果把这一点弄明白,之后的过程就轻车熟路了.这是SPF算法的核心理论,而且这个理论就藏在算法的名字中:”最短路径优先”!一下没弄明白没关系,后面根据提示回顾几遍保你摸透它.
确认了v2以后,按照第一个周期依葫芦画瓢,紧接着就要以v2为中心发散到v4和v5.和之前一样,v0和v1就不用再去了,他们已经是真了,之后不再赘述此原因.刷新min表得:
第三个周期:
在v3,v4和v5中选择最小的v4,v4列为真,原因不再赘述,标为红色如表.再发散v4刷新v3v5v6v7:
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 8 | 5 | 11 | ∞ | ∞ | ∞ |
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 11 | 14 | ∞ |
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 10 | 14 | ∞ |
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 10 | 13 | ∞ |
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 10 | 12 | 17 |
第四个周期:
v3v5v6v7中击中v3为真,发散v3到v6:
第五个周期:
v5v6v7中击中v5为真,发散v5到v7:
第六个周期:
v6v7中击中v6为真,发散v6到v7v8:
第七个周期:
v7v8中击中v7为真,发散v7到v8:
最后一步(第八个周期):
剩下唯一一个非确认字段中v8为真(既是最小也是最大).
到此算法全部结束,怎么样刺激吧,此时min表中记录的就是v0到其余各节点的最短路径度量值.当然人看这篇教程习惯看拓扑图,计算机执行命令时都是从MAP表中读取,后面会有c语言展示.
得到最终的min表只记录了度量值(路径的总长)并没有记录沿途经过的所有节点编号,然而这并不难实现,只需再在程序里添加一个数组沿途记录即可，具体实现方法很简单，就是是：每次刷新min表之后都标明发射源点（上一跳），然后根据上一跳的递归就能沿最短路径回到v0。于是最后得到的拓展min表是这样的：
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 10 | 12 | 16 |
min | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
|---|---|---|---|---|---|---|---|---|---|
v0 | 0 | 1 | 4 | 7 | 5 | 8 | 10 | 12 | 16 |
Last Hop | v0 | v1 | v4 | v2 | v4 | v3 | v6 | v7 |
完美！
总结:
总体回顾一下刚才发生的一切,我们发现在每半个周期结束后,就是在确认最小者为真之前,min表中的节点总是分成三部分:前面红体字;中间黑体字;后面无穷大.分别对应着:已经确认真的最终数值;可能次优的临时数值;还未被发散到的等待数值.如果把每次变化后min表中的三部分节点在刚开始的拓扑图中区分开来,做成九张动态变化图,就能生动形象地表现出SPF算法的根本特点:层层向外扩散,而且整个动画正好见证了一棵SPF树的生长过程.把这些理清楚了有助于理解用Java和C实现的算法语句.
动画效果如下:
!!总共需要循环多少个周期呢?答案是:总共有n个节点就要循环n-1个周期.因为除了第一个节点(v0)默认真,每个周期都要让新的一个节点成真,所以剩下n-1个节点就需要n-1个周期.当然,如果min表中第二部分有两个并列最小的度量值,那么既可以任选一个最小值也可以同时让她们成真,然后分别发散,后者看似可以节省循环次数,但是总工作量并没有节省!!
如果只是想把SPF算法公式给背下来并不困难,你只需要记住每一个循环周期内要做的两件事情就行:先在min表第二部分中寻找最小值并标记为真,再通过被击中的节点发散到它所有邻居并刷新min表.当然还是希望能通过我的讲解,更好地理解算法的智慧.
C语言描述:
1 | #include<stdio.h> |
2 | #define N 50 |
3 | int main() |
4 | { |
5 | int n,m; //节点个数,边的条数 |
6 | int i,j; //for循环参数 |
7 | bool judge[N]; //存放min表每个字段的真假值 |
8 | int MAP[N][N],min[10]; |
9 | int infinity=99999999; //存储一个我们认为的正无穷值 |
10 | |
11 | scanf("%d %d",&n,&m); //输入点数和边数 |
12 | |
13 | for(i=0;i<n;i ) //初始化MAP表 |
14 | for(j=0;j<n;j ) |
15 | if(i==j) MAP[i][j]=0; |
16 | else MAP[i][j]=infinity; //这里考虑到了有向图 |
17 | |
18 | int a,b,c; //MAP读入边权时使用 |
19 | for(i=1;i<=m;i ) //填充每条边权到MAP表中 |
20 | { |
21 | scanf("%d %d %d”,&a,&b,&c); |
22 | e[a][b]=c; |
23 | } |
24 | |
25 | |
26 | for(i=0;i<n;i ) //初始化min数组，这里是0号点到其余各点的初始距离 |
27 | min[i]=e[0][i]; |
28 | |
29 | |
30 | for(i=0;i<n;i ) //judge数组初始化 |
31 | judge[i]=false; |
32 | judge[0]=true; |
33 | |
34 | /*********************以下是SPF算法核心语句*********************/ |
35 | |
36 | for(i=1;i<=n-1;i ) //循环n-1次周期 |
37 | { |
38 | int minimum=infinity; //给寻找min表第二部分最小值的变量赋默认值 |
39 | for(j=1;j<=n;j ) //找出min表第二部分距离0号点最近的节点 |
40 | { |
41 | if(judge[j]==0 && dis[j]<min) |
42 | { |
43 | minimum=min[j]; |
44 | m=j; |
45 | } |
46 | } |
47 | judge[m]=true; //把m拿来做特殊用途:标记新确认真的节点 |
48 | for(j=1;j<=n;j ) //沿着新确认真的节点发散到它的邻居 |
49 | { |
50 | if((e[m][j]!=infinity)&&(!judge[j]))//排除非邻居和已经真的邻居 |
51 | { |
52 | if(min[j]>min[m] MAP[m][j]) |
53 | min[j]=min[m] MAP[m][j]; |
54 | } |
55 | } |
56 | } |
57 | |
58 | /*********************以上是SPF算法核心语句*********************/ |
59 | |
60 | |
61 | for(i=0;i<n;i ) //输出最终的min表 |
62 | printf("%d “,min[i]); |
63 | |
64 | return 0; |
65 | } |
66 |
在OSPF中的应用:
互联网下种类繁多的路由协议中,无论是IGP还是BGP,几乎都是路由器之间通过”口口相传”的方式来寻路的,也就是说,它们根本不知道整个网络地图长什么样.OSPF(开放式最短路径优先协议)提供了与众不同的一种选路方法,也就是SPF算法.为了满足算法的必要条件,在整个ospf网络收敛前期,路由器之间相互交换转发一种叫做”链路状态通告(LSA)”的数据包来表述自己周边的链路情况,足够时间下来每台路由器都有了一张整个区域的线路图和每条链路的带宽开销.后期就是以自己为源并具体进行SPF寻路,于是每台路由器都变成了一个”导航仪”.
自主导航中的实现技术:
如果你要开车从南京雨花台到北京天坛公园,先要在导航仪中设置他们为起点和终点,搜索一条最佳路径.而接下来导航仪负责在电子地图中找一条从雨花台到天坛公园的最短路径.当然这时候导航仪不可能将整个中国明细地图纳入考虑范畴,不然算出结果需要很荒唐的时间.取而代之的是划定一定范围内(包含起点和终点)的道路和交通管制信息,与地点对应存储了相关的经纬度信息.导航仪中有个GPS接收模块,它要接收至少四个不同方位同步导航卫星的信号,并通过这四个信号解一个三元一次方程组,以精确得到你所在的经纬度,继而再显示在地图上.
新SPF算法的优化:
在上述导航仪问题中,如起始点和终点间距离过大,跨省跨州甚至跨国,这时如果按照单纯的SPF计算,纳入考虑范畴的节点数就过于庞大而阻碍效率,造成时间上的浪费.针对这种情况导航仪会将整个世界地图层次化,区域化:省市之间会优选国道和高速公路,跨国越境的话就只能将海关作为”中转站”了.这样一来,导航的最大计算范围也不会超过一座城市的大小.这就是SPF算法新发展趋势的基本思想:即层次化架构地图,减少沿途节点.
结束语:
任何算法都有优劣.SPF算法简单精练理想化,但是在时间复杂度上并不具绝对优势.日常生活中如果只是想让计算机在最短时间内找出任意一条未必要最短的路径,SPF显然就不能满足了.但无论如何,历史悠久的SPF仍然是数学界公认最具代表性的寻路算法.
最后我想说,相比”Dijkstra”,我更喜欢”SPF”这个名字.第一,”SPF”能够简洁明了的暗示算法的精髓部分,第二个原因,我不太倾向于让那些宇宙中永恒存在着的数学理论被冠以发现者的姓名,就像居里夫人曾说过,”我的成就和作品归属于全人类,人们不需要时刻记住我这个发现者的身份”.
温馨提示:文章为作者原创,字字看来皆辛苦,如需转载请标明出处.
