C++最短路径算法研究和程序设计(3)
最短路径时,当终点跳出优先级队列时即可结束。但LS算法不能处理含负权边的网络;
而LC算法处理节点时,可能需要多次进出优先级队列,因此源点到终点的1∶1最短路
径需到算法结束时才能得到；LC算法可处理含负权边的网络[21]。
现如今比较流行的最短路径算法主要有以下三类：
第一类：基于图论理论的算法；
第二类：基于传统人工智能理论的算法；
第三类：基于智能控制技术的算法。
特别是近 10 多年来，智能控制技术在最短路径问题中得到了广泛的应用。人们
的研究兴趣也逐渐的从前两类算法改进到了第三类算法的进一步研究。
而最短路径的研究发展方向主要体现在两个方面：实时性和并行性。 （1）最短路径算法的实时性：目前静态的最短路径算法已经十分完善。但是在
实践中，网络特征可能会时刻发生着变化，这要求最短路径算法必须能够实时的进行
自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的
数据传递路由等方面。在动态最短路径问题中，弧段权值、结点耗费等均为时间 i的
函数，既可以是连续的，也可以是离散的。在假定网络路径权值服从 FIFO 原则的一
致性假设前提下，任何静态的LS和LC算法均可扩展成时间依赖的最短路径算法[21]。
并且国外很多学者针对这些问题提出了动态性最短路径算法的一些解决算法。
（2）最短路径算法的并行化：随着计算机需要处理的数据量急剧增多，传统的
串行计算机所要承担的负荷也是逐渐加重。运行在服务器端的最短路径算法就必须向
基于图分解的并行算法的方向进行发展，这样以满足大量的最短路径实时查询的需要[21]
。关于最短路径并行算法的讨论主要有两种类型，一种是基于较为抽象的并行计算
模型。这种模型不限制处理器的数目，研究给定问题的计算复杂度在并行计算机的情
况下能降到什么程度；如果发现已经达到下界，再设法减少处理器的数目，或者对处
理器之间耦合程度的一些不尽合理或不尽现实的要求；另一类则是研究针对实际的并
行计算系统，其处理器的数目是有限的（至少不能够与问题规模相当），这时研究如
何设计或者实现某个或者某类问题的并行求解；此类并行算法的设计往往还伴有实际
系统上的计算实例和性能分析。而且这类问题由于对处理器的数目进行了合理的限
制，使得并行计算系统在实践中更有价值，这更加说明了最短路径问题算法并行化研
究的趋势所在[21]。
1.3 本文主要完成的工作
此次论文所完成的工作为通过研究经典的最短路径算法 Dijkstra 算法，设计出
一个最短路径算法程序，并且使其能够满足不同人士出行的要求：分别为汽车驾驶员
所希望得到的路程最短路径和时间最短路径，而对于公共交通乘客来说，公交车换乘
次数最短则是其所要的功能并且我此次设计的程序会将换乘次数最少的所有公交线
路全部显示出来以供公交乘客们自己选择。由于城市道路交通的实时性以及随着城市
发展的进程所伴随的道路扩建，文护等情况，城市交通图并不会是一成不变的。为此，
本文还添加了管理员模式设计，使得管理员能够修改内定义的各个邻接矩阵，将交通
路线图实现同步更新，这将会为用户提供极大的便利，相信随着时代的继续进步，最
短路径出行查询会成为所有出行市民必做的一步。
上一篇：车辆主动悬挂系统控制规律设计