C++最短路径算法研究和程序设计(2)
对于私家车或者打的的乘客来说“出行时间最短”是大部分私家车乘客最希望的
第一目标。而“出行路径最短”也是大部分私家车主所要考虑的问题。具体来说驾驶
私家车出行的市民在选择出行方案的选择上有几点要素：
（1）由于现在油价的上涨，部分私家车主会选择行驶路径最短的路线。
（2）现在城市里面的交通压力越来越大，部分路口堵车情况十分的严重，极大的影
响了人们出行的时间。因此大部分私家车主对选择对这些拥堵的路口进行避让，尽量
不去这些路口，选择其他的线路。
（3）由于道路文修或者整改等情况，部分道路可能会封闭起来，这些情况也会使得
私家车主换其他的道路行走。
以上的这些都是私家车出行时所要考虑的因素。
而城市公交线网是分布在城市道路网上的，它是由若干不同的公交路线的集合。
每条线路又是由起迄点及其间的若干个空间位置不同的站点连接而成，因此庞大复杂
的公交线网中，乘客从任意起点出发到目的地之间的路径并不是唯一的。“换乘次数”
是大部分公交乘客在选择出行方案时首先要考虑的因素。
随着计算机科学的发展，人们生产生活经济利润的提高，最短路径问题逐渐的成
为了计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正是因为最短路
径问题在现实生活中的应用如此广泛，研究提高最短路径算法就有着重要的现实意
义。最短路径算法的推行，能够给大家出行带来极方便的查询，推进了城市交通现代
化，说到底就是为了实现人的现代化。城市交通现代化作为城市现代化的重要内容，
首先就应该是是城市居民的生活交通现代化，这是以人为本原则的基本含义和根本需
求。一般来说，实现了居民生活交通现代化（主要是城市交通系统的智能化），便可以满足城市生产和经营交通现代化的要求。在设计公交出行最短路径的时候，通过转
车最少方案实现以人为本的原则。当然，对于私家车出行，我们也可以提供路程最短
和时间最短两种方案。
1.2 国内外发展现状和趋势
早在 20 世纪初人们就认识到了最短路径问题的重要性，当时就有无数的科学家
研究着这一种问题的求解方法。
LS 算法又被称为最短优先搜索算法，最早是在 1959 年，由荷兰的一位计算机科
学家 Edsger Wybe Dijkstra 提出的解决这一种问题的基本思想，并且给出了基础算
法。当时的 Dijkstra 提出的这一种算法主要解决的是某一个固定点到其他所有的点
的最短路径问题。这个算法也就是现在我们所熟知的 Dijkstra 算法。基于堆结构和
桶结构优先级队列的LS算法是研究得最深入、应用也最广泛的LS算法。而Dijkstra
算法的广泛使用使之已经成为了LS算法的代名词，其他的LS算法也大多为Dijkstra
算法的不同的实现方式。值得注意的是，Dijkstra算法描述的是算法的实现方式，与
网络的存储结构完全无关[21]
。
LC算法又被称为列表搜索算法。其代表性的算法包括Bellman Ford Moore算法、
D’Esopo Pape算法、Pallottino算法、门限算法、拓扑排列算法和SLF算法等[21]
。
实际上,所有的 LS 或 LC 算法都可以总结为一种更加一般性的算法的特例。不同
之处在于处理图中所标识的结点时所采用的优先级队列系统各不相同。 LS算法在优先
级队列处理的每一步,都能得到一条由源点到其余节点的最短路径,由此当仅需 1∶1
上一篇：车辆主动悬挂系统控制规律设计