APP下载

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

2017-12-01夏磊

课程教育研究·上 2017年45期
关键词:最短路径

夏磊

【摘要】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.

猜你喜欢

最短路径
“互联网+”时代下滴滴快车补贴方案对打车难问题的影响
Dijkstra算法设计与实现
基于Dijkstra算法的优化研究
图论最短路径算法的图形化演示及系统设计
最佳游览路线生成方案的设计与实现
基于NFC的博物馆智能导航系统设计
XML数据公交信息查询优化算法及实现
基于洪泛查询的最短路径算法在智能交通系统中的应用
求所有最小点成本最短路径算法