基于Dijkstra的多源点最短路径求解算法的设计与分析

祝国明

摘要：Dijkstra是图的单源点最短路径算法，本文介绍利用Dijkstra算法进行多源点最短路径求解的方法，不仅能统计任意两点间的最短路径长度，而且能够求解两点间的具体路径并以堆栈显示，因此有助于算法的学习、比较及拓展，提高计算思维能力。

关键词：Dijkstra算法;最短路径;多源点

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2021）16-0177-02

开放科学（资源服务）标识码（OSID）：

在带权有向图或是无向图中，Dijkstra[1]算法是单源点算法，既然可以实现单源点到任意终点的最短路径求解，那么就可求解并列出任意两点间的最短路径长度表。同时还可以表达任意两点间的具体“路线”，从而得以求解多源点最短路径的问题。

1 需要解决的问题

1）以二维表格形式显示多源点下的最短路径长度，即任意两点间的最短路径表。

2）以二维表格形式显示多源点下的最短具体“路线”表，即任意两点间的最短具体短路径可以通过表格来查看。

3）以堆栈的方式，输出具体两点的最短路径线。

2 问题思维

1）解决多源点最短路径问题

因为能够求解单源点V0到所有终点Vn的最短路径，所以就可以用同樣的方式求解其他源点到所有终点的最短路径问题，只须用循环轮换源点即可。

2）单源点最短路径问题

这个问题可基于Dijkstra算法解决，假定原图矩阵数据为G[N][N]则基本思想如下：

第一，从图的矩阵数据中G[N][N]取出源点V0到各终点Vn “直达”路径Dis[i]=G[0][i]。

第二，设定S[N]为源点V0到终点V1至Vn最短路径是否确定的初态。

第三，采用循环机制，每次从Dis[N]中选取最小的路径权值Dis[i]，此时源点V0到终点Vi 的最短路径确定，修改S[i]标识，找出所有与Vi有关的出度点Vj，如果Dis[j]>Dis[i]+G[i][j]，则修正源点到终点j的最短路径Dis[j]=dis[i]+G[i][j]。

至此，源点到各终点的最短路径长度得以解决。

3）解决路径记录问题

要确切知道，从源点到一终点的具体路径线，可以以记录结点“前驱”的方式进行，模式Dis[j] =dis[i]+G[i][j]表示源点到各终点j的最短路径在不断地修改，因为点j是i的出度，最短路径dis[i]是确定值，所以可以将点i记录为点j的最短路径“前驱”，pre [j]=i+1，从而通过终点可以找出具体路径结果。

4）输出路径问题

由于在最短路径中，各结点只是记录了自身“前驱”结点，因此可以从终点沿路径反向找出全部的路径，而这种特点可以用堆栈结构完成。

3 设计实现

3.1 最短路径长度及最短路径结点“前驱”表

多源点下实现任意点到点最短路径表及任意两点间最短路径中的结点“前驱”表，其对应算法实现如下：

void DjsM（int dis[][N]，int s[][N]，int pre[][N]，int G[][N]）

{ int i，j，k，min，u，v;

for（i=0;i

{ s[i][0]=i;//源点自身最短路径是确定的

for （k=1;k

{ min=max;

for（j=0;j

if（s[i][j]==-1&&dis[i][j]

{ min=dis[i][j];

u=j;

}

s[i][u]=u;//最短路径确定的顶点，加入s集合

for（v=0;v

if（v！=i&&G[u][v]

if（dis[i][v]>dis[i][u]+G[u][v]）//修正源点到v的最短路径dis[v]

{dis[i][v]=dis[i][u]+G[u][v];

pre[i][v]=u+1;//记录对应“前驱”

}

}

}

}

3.2 图的任意两点间的最短路径堆栈式输出

利用最短路径“前驱表”，用堆栈的方式输出源点到终点的路径线。对应处理过程如下：

（1）用于存储图结点序号的堆栈，包括建栈、进栈、出栈基本操作。

struct node//栈模型及实体

{ int st[N];

int top;

int len;

}ss;

void push（int x）//每次进栈一个结点

{  if（ss.top==N-1）

printf（"栈已满！"）;

else

{ ss.top++;

ss.st[ss.top]=x;//进栈一个结点

}

}

void pop（）

{ if（ss.top== -1）//空栈判定

{printf（"栈已空！"）;

return;

}

while（ss.top！=-1）//具体路线显示

{if （ss.top）

printf（"V%d->"，ss.st[ss.top]）;

else

printf（"V%d"，ss.st[ss.top]）;

ss.top--;

}

}

（2）输出源点到终点的具体路线。

ss.len=N;ss.top=-1;

printf（"路径："）;

push（n）;//终点进栈

p=pre[m-1][n-1];//终点的前驱结点序号

while（p）//有前驱，继续

{ push（p）;

p=pre[m-1][p-1];//续找“前驱”，p-1为p结点下标

}

push（m）;//源点进栈

pop（）;//清空栈，得到路线结果

printf（"＼n源点到终点的前驱路径表，元素值为0表示此点无前驱，即“直达”现象＼n"）;

for（m=0;m

{for（n=0;n

printf（"%3d"，pre[m][n]）;

printf（"＼n"）;

}

4 算法測试分析

本算法的测试用例是一个有向或无向图的矩阵数据，算法处理结果分两类，一是图的最短路径长度二维表格，从表中可以直接查看任意两点间的最短路径长度;二是图的最短路径结点“前驱”二维表格，可以查看或是输出任意两点最短路径下的“具体路线”。算法的结果运算正确，多源点最短路径及对应路线求解正确。

5 结束语

本文介绍了基于Dijkstra算法的多源点最短路径及对应路线的求解过程，其问题的求解方法及效果可以类比于Floyd[2]]弗若伊德多源点算法，有利于提高程序思维、计算思维能力，有助于相关算法的学习与借鉴。

参考文献：

[1] 张小艳，李占利. 数据结构与算法设计（C语言版）[M]. 西安电子科技大学出版社，2015.

[2] 顾泽元，刘文强. 数据结构[M].北航出版社，2014.

【通联编辑：王力】