---文章搬家缘故,图片全免了...敬请谅解
独家制作SPF算法深度揭秘,一看就懂!!
摘要:
SPF(shortest path first)算法也叫Dijkstra(迪杰斯特拉)算法,由上个世纪的计算机科学家狄克斯特拉提出,是离散数学中一种经典高效的网络(连通图)最短路径寻路算法.指定一个源点,求出到其余各个顶点的最短路径,也叫”单源最短路径”.
应用场景:
地图导航以及网络路由等.
主要特点:
单个节点拥有上帝视角;以源点为中心向外层层扩展直到终点.
输入:
已知有限个节点和唯一的源点;已知每一条边的权重并且是正数.
循环周期:
先确认距离最短的下一跳,再更新下一跳的邻居.
输出:
得到从源点到剩下所有节点的最短路径信息.
案例拓扑图:
以上面这张复杂的图为例.SPF算法本来是解决有向图的,但因为有向图自然包括了无向图,所以我选择了这张更具代表性的地图.
然后核心问题就是分别求出v0到v1~v8的最短路径.
和Floyd-Warshall算法一样,用二维数组MAP[][]来存放上图每条链路的开销(每条边的权),然后计算机从这个数据库中算出一棵棵SPF树: 注意,这是一张静态表,也就是这张表中数据是不会变化的,为了和后面要用到的动态数组区分开来.
因为是无向图(也可理解为双向图),所以表格沿主对角线两边对称,下三角形就用”/“代表省略.
每个单元格的行和列坐标对应了上图中哪两个节点之间的路径开销,这里认为节点到自己的路径开销为0.剩下不直接相连的两个节点之间都用”∞”表示无穷大.以上就是和Floyd-Warshall表格的不同之处.这张表也就是数字化的拓扑图,便于程序读取其中数据.
然后我们需要一个动态一维数组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表:
到此为止,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:
第四个周期:
v3v5v6v7中击中v3为真,发散v3到v6:
第五个周期:
v5v6v7中击中v5为真,发散v5到v7:
第六个周期:
v6v7中击中v6为真,发散v6到v7v8:
第七个周期:
v7v8中击中v7为真,发散v7到v8:
