资源描述：
《公交车网络的最短路径算法及实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第15卷第9期微机发展Vol.15No.92005年9月MicrocomputerDevelopmentSep.2005公交车网络的最短路径算法及实现112胡霍真,戴光明,李颖(1.中国地质大学计算机系,湖北武汉430074;2.中国建设银行信息技术管理部武汉开发中心,湖北武汉430015)摘要:最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点间的最短路径。为了保
2、证实用性,公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途。关键词:图论;公交车网络;最短路径;广度优先搜索中图分类号:TP3016文献标识码:A文章编号:1005-3751(2005)09-0021-02AlgorithmandRealizationoftheShortestPathinBusNet11
3、2HUHuozhen,DAIGuangming,LIYing(1.FacultyofComputerScience,ChinaUniversityofGeosciences,Wuhan430074,China;2.DevelopmentCenterinWuhan,Info.Techn.ManagementDept.,ChinaConstructionBank,Wuhan430015,China)Abstract:Theshortestpathproblemisaclassicalproblemofthegra
4、phtheory.Itsaimistofindtheshortestpathbetweentwoarbitrarypointsinthegraph.Theshortestpathprobleminthetrafficnetisjusttofindtheshortestpathbetweentwopoints.Toprovethepracticability,thealgorithmoftheshortestpathinbusnetaimstotheleastofnumberofchanging.Thispape
5、rproducesanalgorithmoftheshortestpathinbusnet.Itconsultsthebreadth-firstsearch.Itfindsallthebuseswhichpassbythestartingstationandterminus.Thispapergivesitsrealizationmethod.Secondlyitgivesanexample.Finallyitpointsoutsomenewusesofthisalgorithm.Keywords:grapht
6、heory;busnet;shortestpath;breadth-firstsearch0引言城市之间的公路的长度。如图1所示。最短路径问题现在已经运用于很多领域,例如在旅行而在公交车网络图中,一个顶点表示一个站点,顶点[1]规划系统中,如何快速响应线路询问,就是最短路径计之间的边表示这两个站点之间有公交相连,边上的权值表算问题。在城市的日常生活中,人们通常采用的交通手段示连接这两个站点的公交号,而且可以不只一个公交号。是公交车、轻轨、地铁、小轿车。但是对于在没有轻轨和地显然存在数据库中的任意两个站点都是可
7、以找到一辆公铁的城市中生活的普通大众而言,最常用的还是公交车。汽到达,或者通过转车到达,所以它必然是连通图。如图2人们总是想转最少次数的车或是花最少的时间从起点到所示。达目的地。如何求出从一站点到另一站点的乘坐路线使其经历的转车次数最少呢?这就是要讨论的最短路径问题。1公交车网络的特殊性公交车网络图其实是一个无向连通图,但是它又有其特殊性。它和城市道路网络图是有差别的,在数据结构中图1交通网络图图2公交车网络图的无向图中,一个顶点表示一个城市,顶点之间的边表示这两个城市之间有公路相连,边上的权值表
8、示连接这两个2算法的目的收稿日期:2004-12-11一般在道路网络中最短路径问题就是单纯地求解两作者简介:胡霍真(1978),女,湖北武汉人,硕士研究生,研究方向点间的最短路径,例如文献[2,3]。而在公交车网络中,乘为算法设计与分析。客首先关心的是转车的次数,其次才是路径的长度。因为22微机发展
