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的最短路径的长度。……