《2023年Maple实现基于Dijkstra算法的最短路径》由会员分享，可在线阅读，更多相关《2023年Maple实现基于Dijkstra算法的最短路径（5页珍藏版）》请在金锄头文库上搜索。
1、2023年Maple实现基于Dijkstra算法的最短路径 打开文本图片集 Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，用来解决有向图中最短路径问题，本人运用永久和临时标记的方式，结合数学软件maple中图论程序包networks，解决最短路径问题。 Dijkstra算法 最短路径 mapleG64A 2095-3089（2023）45-0174-02一、引言随之智能手机的高度发展，手机导航已成为有车一族出行必备的工具之一，如何在繁杂的城市道路中找到一条最短、行车最快的路径能够快速到达目的地，是人们非常关心的问题之一。实际上，很多问题都可以归结为一个赋权图的最短路径问题。赋权图
2、的最短路径问题可表述为：设赋权连通图G=（V，E，W），其中V为顶点集，E为边集，W为权（可以是道路长度，修路费用等），在所有顶点vi到顶点vj的路径中，寻找一条长度最短的路径，即一条路径的长度等于路径中所有边的权值之和。二、Dijkstra算法1959年荷兰计算科学家艾兹格迪科斯彻（Edsger Wybe Dijkstra）给出了一个世界上公认最好的计算最短路径的方法，它是对每个顶点做标记，令L（v）代表顶点v的标记，在求解过程中，有些标记被记为临时标记，其余的被记为永久标记。令T表示当前标记为临时标记的顶点集合，算法开始时，所有标记都被标记为永久标记，在每次的迭代过程中，算法将一个顶点的标
3、记从临时标记更改为永久标记。举例来说，假设有A，B，C，D，E，F六个地点，其拓扑结构如图1所示，欲找出A到D的最短路徑。由于这个问题规模比较小，用穷举法可以很容易知道最短路径为AECD，长度为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 所有顶点 xa do L（x）=2.令T为所有顶点组成的集合3.while zT do4.begin5.从T中找出最有最
4、小L（v）的顶点v6.T： T- v7.for 所有与v相邻的顶点 xT do L（x）：minL（x），L（v）+w（v， x）8.end9.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）的最小顶点
5、C（把顶点C图形改为方块），并更新与C相邻的顶点B，E的标注，参见图2，重复上述步骤，找出L（x）的最小顶点E（改为方块），并更新顶点E，B的标注（参见图2）。接着该改顶点E为方块，并更新顶点A的标注（参见图2），这时，就要改A为方块，因A已经做了永久标记，故算法结束，所有由D到A的最短路径长度为9，从A开始顺着标注返回可以得到最短路径为AECD。三、maple实现图论是应用数学和离散数学的重要组成部分之一，maple软件作为一种计算机代数系统，通过20多年的不断发展，已经成为当今世界上最优秀的数学软件之一，其中包含的图论程序包networks，对于研究图论和图论的教学提供了一个强有力的工具。
6、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，
7、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.科技信息.2023（18）.2张小红，张建勋.数学软件与数学实验M.北京：清华大学出版社.2023.
