祝国明

摘要：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]中选……