SPF（Dijkstra）算法完美教程

您所在的位置：网站首页 › spf计算时间 › SPF（Dijkstra）算法完美教程

SPF（Dijkstra）算法完美教程

2023-08-24 06:07| 来源: 网络整理| 查看: 265

SPF(Dijkstra)算法完美教程

独家制作SPF算法深度揭秘,一看就懂!!

摘要:

SPF(shortest path first)算法也叫Dijkstra(迪杰斯特拉)算法,由上个世纪的计算机科学家狄克斯特拉提出,是一种经典高效的网络(连通图)最短路径寻路算法.指定一个源点,求出到其余各个顶点的最短路径,也叫”单源最短路径”.

应用场景:

地图导航以及网络路由等.

主要特点:

单个节点拥有上帝视角;以源点为中心向外层层扩展直到终点.

必要条件:

已知有限个节点和唯一的源点;已知每一条边的权重并且是正数.

循环周期:

先确认距离最短的下一跳,再更新下一跳的邻居.

结果:

得到从源点到剩下所有节点的最短路径信息.

案例拓扑图:

SPF（Dijkstra）算法完美教程_SPF

以上面这张复杂的图为例.SPF算法本来是解决有向图的,但因为有向图自然包括了无向图,所以我选择了这张更具代表性的地图.

然后核心问题就是分别求出v0到v1~v8的最短路径.

和Floyd-Warshall算法一样,用二维数组MAP[ ][ ]来存放上图每条链路的开销,也就是每条边的权:

MAP

∞

注意,这是一张静态表,也就是这张表中数据是不会变化的,为了和后面要用到的动态数组区分开来.

因为是无向图(也可理解为双向图),所以表格沿主对角线两边对称,下三角形就用”/“代表省略.

每个单元格的行和列坐标对应了上图中哪两个节点之间的路径开销,这里认为节点到自己的路径开销为0.剩下不直接相连的两个节点之间都用”∞”表示无穷大.以上就是和Floyd-Warshall表格的不同之处.这张表也就是数字化的拓扑图,便于程序读取其中数据.

然后我们需要一个动态一维数组min[].它的初始状态就是MAP中第二行(v0那一行),末状态就是整个算法要得到的结果:v0到其余所有节点的最短路径开销总值.

初状态:

min

∞

这张表的工作模式可以类比网络世界里各种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

∞

到此为止,SPF算法已经完成了第一个循环周期,即开篇所说的:先确认距离最短的下一跳(即确认真值v1),再更新下一跳的邻居(发散v1并更新min表).专业术语中周期后半部分的”发散”被称为”松弛”,但个人觉得前者更通俗易懂,所以下文我都用”发散”来表达这个过程.接下来进入第二个周期:

此时最小的v2列为真!!(我当时就在这个点上纠结了一个小时…)因!为!通过前两个已经为真的v0和v1发散出去的所!有!路径(止于邻居)都赫然写在min表中(4,8,6),也就是说其他到达v2的路径长度至少也要大于6.大家如果把这一点弄明白,之后的过程就轻车熟路了.这是SPF算法的核心理论,而且这个理论就藏在算法的名字中:”最短路径优先”!一下没弄明白没关系,后面根据提示回顾几遍保你摸透它.

确认了v2以后,按照第一个周期依葫芦画瓢,紧接着就要以v2为中心发散到v4和v5.和之前一样,v0和v1就不用再去了,他们已经是真了,之后不再赘述此原因.刷新min表得:

min

∞

第三个周期:

在v3,v4和v5中选择最小的v4,v4列为真,原因不再赘述,标为红色如表.再发散v4刷新v3v5v6v7:

min

∞

第四个周期:

v3v5v6v7中击中v3为真,发散v3到v6:

min

∞

第五个周期:

v5v6v7中击中v5为真,发散v5到v7:

min

∞

第六个周期:

v6v7中击中v6为真,发散v6到v7v8:

min

第七个周期:

v7v8中击中v7为真,发散v7到v8:

min

最后一步(第八个周期):

剩下唯一一个非确认字段中v8为真(既是最小也是最大).

到此算法全部结束,怎么样刺激吧,此时min表中记录的就是v0到其余各节点的最短路径度量值.当然人看这篇教程习惯看拓扑图,计算机执行命令时都是从MAP表中读取,后面会有c语言展示.

得到最终的min表只记录了度量值(路径的总长)并没有记录沿途经过的所有节点编号,然而这并不难实现,只需再在程序里添加一个数组沿途记录即可,这里就不具体展示了.

总结:

总体回顾一下刚才发生的一切,我们发现在每半个周期结束后,就是在确认最小者为真之前,min表中的节点总是分成三部分:前面红体字;中间黑体字;后面无穷大.分别对应着:已经确认真的最终数值;可能次优的临时数值;还未被发散到的等待数值.如果把每次变化后min表中的三部分节点在刚开始的拓扑图中区分开来,做成九张动态变化图,就能生动形象地表现出SPF算法的根本特点:层层向外扩散.把这些理清楚了有助于理解用Java和C实现的算法语句.

!!总共需要循环多少个周期呢?答案是:总共有n个节点就要循环n-1个周期.因为除了第一个节点(v0)默认真,每个周期都要让新的一个节点成真,所以剩下n-1个节点就需要n-1个周期.当然,如果min表中第二部分有两个并列最小的度量值,那么可以同时让她们都成真,然后分别发散,这样的话可以节省循环次数,但是总工作量并没有节省!!

如果只是想把SPF算法公式给背下来并不困难,你只需要记住每一个循环周期内要做的两件事情就行:先在min表第二部分中寻找最小值并标记为真,再通过被击中的节点发散到它所有邻居并刷新min表.当然还是希望能通过我的讲解,更好地理解算法的智慧.

C语言描述:

#include

#define N 50

int main()

{

int n,m; //节点个数,边的条数

int i,j; //for循环参数

bool judge[N]; //存放min表每个字段的真假值

int MAP[N][N],min[10];

int infinity=99999999; //存储一个我们认为的正无穷值

scanf("%d %d",&n,&m); //输入点数和边数

for(i=0;i初始化MAP表

for(j=0;j

if(i==j) MAP[i][j]=0;

else MAP[i][j]=infinity; //这里考虑到了有向图

int a,b,c; //MAP读入边权时使用

for(i=1;i

【本文地址】

公司简介

联系我们