内容发布更新时间 : 2024/9/18 16:25:29星期一 下面是文章的全部内容请认真阅读。
摘 要： 改进的dijkstra算法和floyd算法是求两点间最短距离和最短路径的最简单有效的方法。但是当图的顶点个数为上万或者几十万时，计算两点间的最短距离的时间开销将是非常巨大的。利用加权图的子图来解决这一问题。
关键词： 最短路径；加权图；子图；dijkstra算法；floyd算法
中图分类号：tp301.6 文献标识码：a 文章编号：1671－7597（2012）0220091－02 0 引言
交通系统中的最优路径算法等同于图论中的最短路径算法，根据不同的具体要求可以是长度最短或行驶时间最短。dijkstra算法和floyd算法是求解最短路径问题中最简单有效的两种算法。但是当加权图中的定点数非常大时，时间开销也会非常大。本文将讨论并解决这一问题。
1 改进的dijkstra算法
传统dijkstra算法是求解带权图g中从某一源点到其余各点的最短路径的一种有效算法，能够得到最优解.针对我们在公交换乘中最常需要计算的两点间的最短距离和路径，将传统的dijkstra算法进行改进。算法的基本思想如下：输入起始节点s ，输入终点v。1）从存放图g中所有节点的集合u中找出距起始点最近的子节点；2）遍历考察这个点的子节点距离起始点的距离值，求出最小值；3）把该最小值放入集合s中，把该子节点放入集合h中，重复上述步骤直到集合u为空，或者找到终点。改进的dijkstra算法实例分析：设加权图g（如图1）：
应用改进的dijkstra算法编程实现任意两点间的最短路径求解，例如求解图中1到7的最短路径运行程序结果为：最短路径为1 3 5 7，最短距离为9.00000。 2 floyd算法
floyd算法则又称为插点法是一种用于寻找给定的加权图中顶点间最短路径的算法。算法的基本思想是：加权图中两个结点之间间的最短路径有两种可能：1）相邻时最短，2）以通过几个中间结点为跳板时距离最短。算法每次以其中一个结点为跳板，如果以该节点为跳板后两结点间路径缩短，则更新这两个结点间的路径，直到测试完成每个充当跳板的结点，并且记录经过的最短路径。例如上述加权图g，我们可以用floyd算法编程实现图g中任意两点间的最短路径和最短距离：
d为各结点间的最短距离，r为最短路径。
根据不同的需求，利用上述两种算法，可以求出加权图中任意两点间及各点间的最短距离和最短路径 3 子图的应用
对于一座大中型城市，地理节点数目可能达到几万个到几十万个，利用上述两种算法计算最短路径的时间开销将是非常巨大的.图2取自于我国某市的部分街巷图。如果我们要查询从a地到b地的最短路径，很显然a-c-b不会是最短路径，a到b的最短路径a-a1-a2……an-b，其中站点a1，a2，a3，……an必然在a地到b地的附近。
实例1：在加权图h中，求4到11的最短距离。那么4到11的最短路径必然不包括17到22这些点。所以我们在计算最短路径时就不必考虑17到22这些点，只需考虑1到16这些点即可。亦即求4到11的最短距离我们只要遍历加权图h的子图j即可。我们利用改进的dijkstra算法加以验证。加权图h中结点4到结点11的最短距离为8，最短路径为4，8，
11，加权图j中结点4到结点11的最短距离为8，最短路径为4，8，11。 实例2：利用dijkstra算法来验证图6加权图k中结点4到结点7的最短距离为14，其最短路径为：4，3，2，1，12，13，7，但是用加权图k的子图l来求结点4到结点7的最短距离和最短路径，显然最短距离16，最短路径4，3，9，8，7与正确结果存在误差。 4 结论
为减少上诉误差，首先我们在将公交线路图抽象为加权图的过程中应该坚持：1）大范围上两结点间的距离越小，两结点间的序号越接近；2）取加权图的子图时应尽量大，子图的选取对计算误差有着决定性的影响，子图越大，误差越小，相对的计算时间也将会越长。所以，选取合适的子图对于减少计算误差和缩短计算时间非常关键。
基金资助：中北大学校基金和山西省自然科学基金（编号2009011018-3）
参考文献：
[1]章永龙，dijkstra最短路径算法优化[j].南昌工程学院学报，2006，25（3）：30，32.
[2]thomas h cormen,charles e leiserson，ronold l rivest,et a1.imrⅸtuction to al@ritlun[m].北京：高等教育出版社，2001.
[3]徐风生，求最短路径的新算法[j].计算机工程与科学，2006（2）：84-85.
[4]李洪波、王茂波，folyd最短路径算法的动态优化，计算机工程与应用，2006（34）：60-63.
[5]李健，基于dijkstra最短路径算法的优化研究[j].渭南师范学院学报，2009（5）：61-64.
作者简介： 韩慧玲（1983-），女，硕士研究生，研究方向：计算机中的数学问题；导师：胡红萍（1973-）女，副教授，硕士生导师。