Maple实现基于Dijkstra算法的最短路径

夏磊

【摘要】Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，用来解决有向图中最短路径问题，本人运用永久和临时标记的方式，结合数学软件maple中图论程序包networks，解决最短路径问题。

【关键词】Dijkstra算法 最短路径 maple

【中图分类号】G64 【文献标识码】A 【文章编号】2095-3089（2017）45-0174-02

一、引言

随之智能手机的高度发展，手机导航已成为有车一族出行必备的工具之一，如何在繁杂的城市道路中找到一条最短、行车最快的路径能够快速到达目的地，是人们非常关心的问题之一。

实际上，很多问题都可以归结为一个赋权图的最短路径问题。赋权图的最短路径问题可表述为：设赋权连通图G=（V，E，W），其中V为顶点集，E为边集，W为权（可以是道路长度，修路费用等），在所有顶点vi到顶点vj的路径中，寻找一条长度最短的路径，即一条路径的长度等于路径中所有边的权值之和。

二、Dijkstra算法

1959年荷兰计算科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）给出了一个世界上公认最好的计算最短路径的方法，它是对每个顶点做标记，令L（v）代表顶点v的标记，在求解过程中，有些标记被记为临时标记，其余的被记为永久标记。令T表示当前标记为临时标记的顶点集合，算法开始时，所有标记都被标记为永久标记，在每次的迭代过程中，算法将一个顶点的标记从临时标记更改为永久标记。举例来说，假设有A，B，C，D，E，F六个地点，其拓扑结构如图1所示，欲找出A到D的最短路徑。

由于这个问题规模比较小，用穷举法可以很容易知道最短路径为A→E→C→D，长度为9。

在Dijkstra算法中，如果L（v）是顶点v的永久标记，那么L（v）就是从起点到v的最短路径的长度。要在一个连通的赋权图中寻找顶点A到D的最短路径长度，边（i， j）的权值w（i， j）>0，且顶点x的标记为L（x），此时Dijkstra算法可详细描述为：

1.L（a）=0；for 所有顶点 x≠a do L（x）=∞

2.令T为所有顶点组成的集合

3.while z∈T do

4.begin

5.从T中找出最有最小L（v）的顶点v

6.T： T- {v}

7.for 所有与v相邻的顶点 x∈T do L（x）：min{L（x），L（v）+w（v， x）}

8.end

9.end.

下面求图1由顶点A到D（即D到A）的最短路径及其长度：依次执行到算法第五行（此时图的状态如图2①），此时T为所有顶点，其中具有零时标记的顶点为D（为了区分顶点是否已被考察过，考察过的顶点我们用方块表示），修改T为{C，F，B，E，A}，更新与D相邻的顶点C，F的标记L（C）=min{∞，0+3}=3，L（F）=min{∞，0+7}=7，并标注顶点C，F，此时图的状态如图2②，其中标注“D，3”表明它的长度和它从D被标注的事实。接下来，在T中找标记L（x）的最小顶点C（把顶点C图形改为方块），并更新与C相邻的顶点B，E的标注，参见图2③，重复上述步骤，找出L（x）的最小顶点E（改为方块），并更新顶点E，B的标注（参见图2④）。接着该改顶点E为方块，并更新顶点A的标注（参见图2⑤），这时，就要改A为方块，因A已经做了永久标记，故算法结束，所有由D到A的最短路径长度为9，从A开始顺着标注返回可以得到最短路径为A→E→C→D。

三、maple实现

图论是应用数学和离散数学的重要组成部分之一，maple软件作为一种计算机代数系统，通过20多年的不断发展，已经成为当今世界上最优秀的数学软件之一，其中包含的图论程序包networks，对于研究图论和图论的教学提供了一个强有力的工具。Networks提供了非常丰富的函数，在绘制简单图及进行Dijkstra算法时，我们需要用到一下函数：

在使用networks中的命令之前，需装载该程序包，即执行with（networks），首先画出图1的简单图（图3），命令如下：

>with（networks）：

new（G）：

addvertex（{A， B， C， D， E， F}， G）：

addedge（[{A， B}， {A， E}， {B， C}， {B， F}， {E， F}， {E， C}， {C， D}， {F， D}]， weight=[4， 5， 3， 6， 8， 1， 3， 7]， G）：

>draw（G）；

然后找出图中边的长度：

>eweight（G）；

table（[e13=8，e2=5，e12=6，e1=4，e9=4，e14=1，e4=6，e7=3， e16=7， e8=7， e11=3， e15=3， e6=1， e5=8， e3=3， e10=5]）

使用maple提供的shortpathtree（G， v）命令（使用Dijkstra算法）求解最短路径问题，并找出最短路径（图4）：

> T：=shortpathtree（G， A， W）：

>draw（T）；

最后利用vweight（v， G）命令得到A到D的最短路径长度为9。

>vweight（D， T）；

四、结论

进入二十一世纪，随着多媒体技术和数学软件的迅速发展，计算机代数系统maple能够处理图论等数学分支，这是它优于其他数学软件的特点之一，利用maple软件进行图的构建，帮助人们解决最短路径问题，进行图论计算，理解图论的概念和方法，提供了有效的手段。这种利用CAS（Computer Algebra System，计算机代数系统）进行数学研究的方式，在当前信息化快速发展的时代，值得提倡和推广。

参考文献：

[1]部亚松.VC++实现基于Dijkstra算法的最短路径[J].科技信息.2008（18）.

[2]张小红，张建勋.《数学软件与数学实验》[M].北京：清华大学出版社.2004.