关于最短路算法的一些研究.pdf

《关于最短路算法的一些研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第17卷第4期西安文理学院学报：自然科学版Vo1．17No．42014年10月JournalofXi’anUniversity(NaturalScienceEdition)Oct．2014文章编号：1008-5564(2014)04-0032-04关于最短路算法的一些研究张岩(西安文理学院数学与计算机工程学院，西安710065)摘要：首先引出图论模型这一基本概念，然后简单介绍了最短路问题的分类，在此基础上具体阐述并且分析了求最短路径的常用算法——Dijkstra算法、Floyd算法和Ford算法．最后主要对Dijkstra算法在公交网络中的应用进行了研究和分析，

2、并且列举了最短路算法在其他领域中的一些应用．关键词：最短路；Dijkstra算法；Floyd算法中图分类号：TP301．6文献标志码：AOntheAlgorithmsinCalculatingtheShortestPathZHANGYan(SchoolofMathematicsandComputerEngineering，Xi’anUniversity，Xi’an710065，China)Abstract：Wegiveabriefintroductiontothegraphmodel，theclassificationoftheshortest—pathissu

3、eandelaborateonthecommonlyusedalgorithms：Dijkstraalgorithm，FloydalgorithmandFordalgorithm．EmphasishasbeenputontheapplicationofDijkstraalgorithmintransitnet-work．Wehavealsointroducedtheapplicationsoftheshortest—pathalgorithminotherareas．Keywords：shortestpath；Dijkstraalgorithm；Floydalg

4、orithm最短路径问题在计算机科学、交通工程学、运筹学、地理信息学等学科的研究中一直是一个热点问题．所有的路径中距离最短的一条，我们把它称作最短路径．而最短路径问题不仅仅指的是距离上的最短路径，更能够引申到其他意义上．相应地，最短路径问题在实际的应用中就成为最快路径问题、最低费用问题等．1最短路问题背景为了简化问题，很多问题我们通过建立数学模型突出要点，而建立图论模型的目的则是一样的，便于更加深入地研究问题的本质，例如根据图论的基本理论来分析图论模型性质，或者根据典型的图论算法对图论模型进行求解，图论模型中的相关算法及理论其他模型不具备．有向加权图G=(，E)

5、，在此基础上定义的加权函数：E—R为从边到权值的映射．路径P：(V，⋯，，)的权是指图中所有边的权值之和：收稿日期：2014-07—10基金项目：西安市科技计划项目(CXY1134WL14)作者简介：张岩(1982～)，女，陕西蓝田人，西安文理学院数学与计算机工程学院讲师，硕士，主要从事无线传感器网络研究．第4期张岩：关于最短路算法的一些研究33pLVi一1，i定义顶点到顶点间最短路径的权值为：[min{w(p)：Ⅱ)存在由u到的通路1，、oL，1∞不存在由到的通路．『从顶点u到顶点的最短路径定义为权(P)=(u，)的任何路径．研究的目的是从起点到目标点之间找一

6、条最短路径．权不仅仅是距离，经常为一种度量方法，而它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式．2最短路问题的几种分类2．1单源最短路径问题这种问题是最短路径问题中最基本的一种，主要是求某个固定点开始到所有点的最短路径．2．2单汇最短路径问题问题的本质是求所有顶点到某个点的最短路径．对于求所有点到某个点的最短路径，反向思考即求从此点出发到其它顶点的最短路径，是一种进行“反向”操作的过程．2．3单个确定源点到一个汇点的最短路径问题这个问题其实和单源最短路的思维方式几乎一致，研究到目前为止仍然认为解决这个问题的方法应用求单源最短路的模式

7、是最好的．2．4求任意顶点之间的最短路径问题首先将问题简化为求每个节点开始求单源最短路，最后逐一计算．但是此方法复杂度较大，因而就有一种特殊的方法来求解此问题，不过比较重要的一点是在时间复杂度上要落后于多次单源最短路的方法．3几种常用算法3．1迪杰斯特拉(Dijkstra)算法Dijkstra算法用于计算单一节点到其他所有节点的最短路径，是一种求单源最短路的算法．设G=(，)是一个带权有向图，现求初始源点到每个终点的长度．把图中顶点集合分成两组，一组为已求出的最短路径的集合(用5表示)，另一组为未确定最短路径顶点的集合(用一．s表示)，初始时S={。}，—S={

8、其余顶点}，若从到i有直