最短路径算法分析及其在公交查询的应用 陈箫枫.pdfVIP

维普资讯 2001在 工 程 图 学 学 报 2001 第 3期 J0URNAL 0FENGINEERINGGRAPHICS No．3 最短路径算法分析及其在公交查询 的应用 陈箫枫 蔡秀云 唐德强 (华南理工大学，广州 510641) 摘 要 ：通过对常见的最短路径及其算法的分析，指 出以往的最短路径 算法不能实现I／厶＼交路线的查询，提 出更适合公交查询的最短路径算法以及广州市 公交线路查询系统的实现。 关 键 词：最短略径：公交查询 中图分类号：TB23 文献标识码 ：A 文 章 编 号：1003-0158(2001)03—0020-05 1 常见的最短路径 问题及算法 ll 在实际中常见的最短路径 问题 例如，如果司机用汽车运输货物从 A 城到 城，他就会考虑走路程最短或者时间最少 的道路 这是考虑路程或时间的最短路径 问题 又例如，要在 A地到 地之间铺设煤气管道 。在 A，B地 问的长方形地区划分格子点． 根据地形、土壤、是否经过江河、泥塘、农 田、村庄、郊区、城镇、公路、铁路等各种情况， 将从一格子点至另一格子点的铺设费用估计出来。求：由A 地到 B 地铺设煤气管道经过哪 些格子点使总的造价最小。这是考虑费用的最短路径 问题 。 另外在线路安排、设备更新、厂区布局、城市规划 、电子导航 、交通转车等方面均 需 要考虑到最短路径 问题 l2 赋权图的最短路径 设有图G，对 G 中的每一条边 (， )，相应地有一个数 L ( ， )称为边的权。图 G连同在它边上的权被称为赋权 图。一条边的权也说成它的长。一条道路 ， ．…， 的长是 “上所有长的和 ，即L ( ， )+ ( ， )+…+ ( -1， )。 在赋权 图中给定一个始点 及终点 。所谓最短路径 问题就是在 ( ， )道路集合{P} 中，寻求长为最小的路径 ，这样的路径称为从 到 的最短路径。从 到 的最短路径长 度 即最短距离记作d( )。 赋权 图中的权可以表示两个顶点间的距离，或者途 中所经的时间，或者交通 费用等 。 此时路径长度的度量不是路径上边的数 目，而是路径上边的权 (距离、时间、费用等)之和。 收稿 日期：2001—03—06 作者简fr：陈莆枫 (1974-)．男．广 西埔壮^．砸士研究生．主要研究领域舟计算机图形学a 维普资讯 第 3期 陈箫枫等：最短路径算法分析及其在舟交查询的压用 2l 例如图 l，每个顶点表示城市，两个顶点构成的边表示两 城市 间的道路 ，边上的数字也就是上面说的权表示两个城市之 间的距离 (公里)，如果用汽车运输货物从J4城到H城，司机 ^ H 就会考虑走路程最短的道路 ，那么最短路径是哪…条呢?应该 足 A一 一D一 ， 而且最短距离 d (， )=上 (，B)+上 ( ．D)+L (D． )=1oo+10O+100=300公里 F 13 迪杰斯特拉(Dijkstra)最短路径算法 图 1 睦权图的最短路径 寻找两顶点问的最短路径的算法很多， 目前公认最好的算法是迪杰斯特拉 (Dijkstra) 在 1959年提出的，它不仅求出从始点到终点的最短路径，而且最后所得到的实际上是始点 到各顶点的最短路径 对Dijkswa算法进行补充得出的步骤如下： 第一步 初始化。 f1，2，…，Ⅳ‘}， =f一 ，D [，l= ，J，y[11=，，其