Dijkstra算法计算最短路的教学探析
2022-01-08丁学利
丁学利
(阜阳职业技术学院，安徽 阜阳 236031)
图论是离散数学中实践和理论融合较强的一部分内容,尤其是最短路的计算问题,其实际应用范围较为广泛。在现实生活中的许多问题,如交通网中的最短路问题,物流中的优化问题,计算机学科相关问题的研究,都涉及到图论中的最短路的计算。计算最短路的算法最常用的是Dijkstra算法,此外还有Floyd算法等。Dijkstra算法是最早研究最短路的有效算法之一,它是计算从带权图中的某一固定结点(源点)到其余结点的最短路径,但要求权值不能为负。许多图论教材对Dijkstra算法都进行了介绍,但有些讲解较简洁,学生不易理解,再加高职数学基础较薄弱,因此学生在实际计算的时候却经常出现错误。对此,本文通过对Dijkstra算法从不同视角进行直观、有效的讲解,将有助于学生发散思维的培养和锻炼,同时对学生的学习兴趣和教学质量的提升也具有促进作用。
1 Dijkstra算法的一般步骤
设图G
=(P
,E
)为一个带权无向图(或为有向图,本文主要讨论无向图),P
为结点集,E
为边集。Dijkstra算法的一般步骤如下:Step 1:给定初值,令A
={p
},d
(p
)=0,B
=P
-A
。若p
与B
中的结点有边直接相连,则记为正常权值,否则其权值记为∞;Step 2:计算p
与B
中结点的距离,然后选取一个距离最短的结点p
。此时,A
=A
∪{p
},B
=V
-A
;Step 3:以p
作为新的中间点,继续计算p
与B
中结点的距离,寻找距离最短的结点p
。若从p
到结点p
的距离(经过结点p
)比不经过结点p
短,则更新结点p
的距离值,否则不更新;Step 4:若B
=ø,则停止,否则转Step 2继续寻找。用上述步骤1-4计算的距离d
(p
)即是p
到p
的最短路的权,由p
的父亲标记向回追溯到p
, 即可得p
到p
的最短路径。下面将从不同角度对Dijkstra算法进行教学探析。2 实例教学探析
2.1 实例1
表示结点为p
(i
=0,1,…,5)的带权无向图如图1所示。每个结点代表一个城市,结点间连线上的数字表示城市之间的距离。试用Dijkstra算法计算p
到p
(i
=1,…,5)的最短路径和距离。
图1 6个城市的道路图
(1)表上作业法。可将Dijkstra算法步骤用表格列出,具体过程如表1所列。表1中每一行用带方框标识的数字表示在迭代过程中寻找路径权的最小值。最短路径可表示为该最小数字首次出现前的最短路径加上该结点组成。
表1 表上作业过程
(2)图上标号法。Dijkstra算法的结果也可在图上用标号(i
,d
)标出。其中,d
表示从源点p
到结点p
的最短路的权;i
表示p
的父亲点,用以追溯最短路径。每次迭代都会得到一个新的永久标号,最终将会得到一棵以p
为根的生成树从而得到任意一个结点与根结点p
之间的最短路径。具体寻找过程,如图2(a)图2(f)所示,图中的粗实线表示寻找到的最短路径。
图2 图上标号过程
2.2 实例2
某化工厂为了保障正常生产,需要对26个巡检点进行例行巡检,且要求巡检工人从调度中心(22)开始巡检,详细的巡检路线图,如图3所示。试给出巡检人员从调动中心(22)到其余巡检点的最短路径。
图3 工厂巡检路线图
利用Dijkstra算法可求得巡检中心22到其余巡检点的最短路。由于巡检点较多,使用流程表法较繁琐,而表上作业法所需表格较大,可考虑图上标号法。图上标号的开始如图4左图所示,结束如图4右图所示,中间标号过程省略。图4(右图)中的粗实线即是用图上标号法得到的从巡检中心22到其余各点最短路的生成树,具体的最短路径和距离,如表2所列。
图4 图上标号法的开始(左图)和结束(右图)
表2 最短路径和最短距离
3 结束语
本文分别运用表上作业法和图上标号法对Dijkstra算法进行了教学探析,但每种方法都有优缺点。图上标号法虽然简洁明了,但由于新老标号不断更新,需集中精力、保持清醒的头脑才不会出错。表上作业法可以在表上直接进行迭代，比图上标号法更具有秩序性和规则性,较适合复杂问题的推算,但结点个数较多时,所需表格会非常大。若结点个数非常多,可考虑MATLAB编程方法解决,但MATLAB编程要求学生具备一定的编程基础。此外,在高职数学教学中适当引入数学建模竞赛试题(如实例2)将有助于提升学生对数学的学习兴趣和应用意识,同时也有助于培养学生的发散性创新思维和动手实践能力。
