最短路径问题是旅游行程规划的基本科学问题之一，并已成为城市道路交通、网络通信、城市规划等许多网络优化问题的子问题。在传统的最短路径问题中，研究较多的还是S-D对（源—目标点）之间的静态最短路径，集中在以下几个方面：一是针对实际网络特征优化存储结构，减小存储空间，提高算法的运行效率；二是采用有损算法，如限制搜索范围、层次搜索法，以减少算法的搜索规模；三是采用启发式搜索策略以减少搜索空间；四是改进优先级队列结构，提高算法的运行效率。

最短路径问题在计算机科学、交通工程、通信工程、系统工程、运筹学等领域得到了普遍的研究。由于各领域问题特征、网络特征等纷繁复杂，最短路径算法也表现出多样性。最短路径常按如下方式进行分类：按弧的权值是常值还是变量，分为静态最短路径问题和时变最短路径问题；按照源、目标节点的多少，可分为单源最短路径问题及全源最短路径问题；按弧的权值是时间确定的还是非确定的，分为确定型最短路径问题和随机最短路径问题；按照计算方法，分为串行最短路径算法和并行最短路径算法；按照网络规模大小，分为小规模网络最短路径问题和大规模网络最短路径问题。上述各类问题之间相互组合又产生了多种新的最短路径问题。

与全源最短路径问题相比，单源最短路径问题更具有普遍意义。单源最短路径问题的算法有很多种，从早期的基于限制条件的深度优先搜索算法、基于有向无环图的动态规划法、基于邻接矩阵的算法、到最大相关边法、最大相关点法、基于邻接表的算法、基于超图数据结构的深度优先椭圆搜索算法等。针对不同的网络特征、应用需求及具体的软硬件环境，各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。其中，采用贪心及启发策略的Dijkstra算法是目前已知的理论上最完善的算法，它以极强的抗差性而得到广泛的普及和应用。遗传算法、蚁群算法是基于生物进化原理的全局性优化算法，在一系列复杂的系统优化问题求解中取得了很大成效，成为解决旅行商问题、二次分配问题、最短路径问题、网络路由问题等典型问题的一类新型的强有力算法。

1.静态最短路径算法

如果网络中所有弧的权值都是常数，这样的网络称为静态网络。相应的，求解静态网络中两点之间（或者从源节点到网络中所有其他节点，或者所有节点之间）最短路径的算法，称为静态最短路径算法。静态最短路径算法属于传统最短路径算法，对该类算法的研究已有相当长的历史。美国著名数学家、动态规划的鼻祖R.Bellman在1958年研究了这一问题。通过基于不同特性的随机网络的试验发现，没有哪一种算法能够在任何情况下都保持优势。针对不同规模的道路网和寻优需求的测试结果显示，可以根据道路网弧长的分布范围选择合适的算法，并且TWO-Q（Two Queue）比较适合计算单源节点到其他所有节点间的最短距离。

基于路网规模控制的优化。产生于计算机科学及运筹学的最短路径算法，因只考虑网络的拓扑特征或阶段特征，而忽略了网络的空间分布特征，使得其搜索过程缺乏方向性，最终得到的都是一棵以源点为根的最短路径数，即使构造此路径数的过程在到达终止节点后就结束，依然有大量的计算是冗余的。因此，在对最短路径算法的研究过程中提出了有损算法——以牺牲一定的精度为代价，来缩小路网搜索规模，减少搜索节点数，提高算法的执行效率。因为有损算法中减小了搜索范围，因此不能保证找到的是最短路径，可能是次短路径。目前控制路网规模的典型算法有限制搜索区域最短路径算法和层次搜索法。

层次搜索法是根据分层和空间分解的道路网络模型提出的一种新的车辆路径规划算法。分层搜索算法由具有分层结构的地图数据库作为辅助，首先在较高层的空间，如主干道进行搜索，然后才是次干道，这样可以减少问题的复杂性。而分解搜索的基本思想是：根据道路网络的自然分解特性，将原始网络分解成若干个小的子网，通过适当地构建边界图，就可以将一个对原图进行最短路径查询的问题分解为一系列对更小图的最短路径查询问题。限制搜索区域的算法目的是为了在大型的道路网中确定一个较小的范围，使任意给定的两点之间的最短路径落在该范围内的可能性较高。限制搜索区域的算法的内容就是研究怎样找出这个范围，该范围与源点、目标点的相对位置有什么关系。(www.daowen.com)

2.时变、随机网络最短路径算法

如果网络中弧的权值是随时间变化的，即弧的权值是时间的函数，则到达弧尾节点的时刻不同相应的弧的旅行时间也不同，这样的网络称之为时变网络或时间依赖的网络（以下简称TDN网络），有些文献中称之为动态网络。在网络中如果用随机变量而不是用简单的标量表达边权，该随机变量服从离散的或连续的概率分布函数，称这样的网络叫随机网络。如果网络中弧的权值是随时间变化的，并且不同时间取不同的概率分布，这样的网络称之为时变、随机网络或称之为随机时间依赖网络。

随着智能交通系统，特别是路径导航系统的快速发展，动态交通分配问题越来越受到人们的关注。在智能交通系统中，路径规划的主要衡量标准是源点至目标点间的旅行时间。由于道路交通流具有动态变化的特性，使得旅行时间也是实时变化的，因而有必要将时间维引入网络建模。在智能交通系统中，车辆路径规划不仅具有时变性，而且具有随机性。由于未来旅行时间（或代价）存在的潜在随机性，不完全的先验信息以及预测未来旅行时间（或代价）的不准确性，导致弧的旅行时间（或旅行代价）存在某些不确定性，因而将网络弧段的旅行时间表示成时间依赖的随机变量能够更好地描述实际的交通网络。

3.基于蚁群算法、遗传算法的最短路径

蚁群算法是20世纪90年代初由意大利学者M.Dorigo和Maniezzo等首先提出的，模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法。他们充分利用蚁群搜索食物的过程与旅行商问题（Traveling Salesman Problem TSP）之间的相似性，很好地解决了TSP问题。随后，蚁群算法被用来求解二次分配问题、车辆路径规划问题、车辆作业调度问题等，显示出蚁群算法在求解复杂优化问题方面的优越性。蚁群算法具有很强的发现较好解的能力，是一个增强型学习系统，具有分布式计算特性和很强的鲁棒性，且易于与其他优化算法融合。然而，蚁群算法存在的搜索时间过长、易于停滞的问题，限制了这一算法在实际系统中的应用。为了克服这些缺点，众多学者提出了改进算法。蚁群系统（Ant Colony System，ACS）算法，蚂蚁在寻找最佳路径的过程中只能使用局部信息，在所有蚂蚁寻优过程结束后，只对过程中发现的最佳路径上的信息素浓度进行加强，以加快收敛速度。最大-最小蚂蚁系统（Max-Min Ant System，MAS）算法，该算法只允许在产生最好结果的路径上进行信息素更新，同时对路径上的信息素进行最大、最小值限制，这在一定程度上避免了搜索中算法过早收敛于并非全局最优的解早熟、停滞现象，但当解的分布较分散时收敛速度较慢。

遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法，该算法最早由密歇根大学的Holland教授（1975）提出。这一新的全局优化搜索算法一经提出，就以其简单通用，鲁棒性强，适于并行处理等特点受到国内外学者的普遍关注，并在计算机科学、优化调度、运输问题、组合优化等领域得到广泛的应用研究。基于遗传算法解决经典最短路径、提高网络路径搜索效率的措施主要集中在以下几个方面：①染色体编码和种群的初始化过程；②交叉操作过程；③变异操作过程。力求在每个重要的环节上保证染色体对路径表示的合理性，能够大大提高算法的搜索效率和收敛速度。针对图论中的最短路径问题，采用等长染色体编码方式和较为简单的交叉、变异操作，并在遗传迭代的过程中加入个体求优自学习过程。在静态环境下机器人全局路径规划的遗传算法中，将需规划路径的二维编码简化成一维编码，并把免碰撞要求和最短路径要求融合成一个适应度函数。一种基于优先级的染色体间接编码方案，用来表示网络图中的可能路径。采用非等长染色体编码方式表示路径并对交叉和变异后的染色体进行修正，保证了在迭代的过程中每条染色体所表示的路径的有效性，从而提高了搜索的效率，加速了收敛过程。在动态网络最短路径问题中运用随机Dijkstra算法解决了遗传算法初始种群的产生问题，通过动态地调整遗传算子或采用新的遗传算子保证了种群的多样性，克服了过早收敛并加快了搜索速度。遗传算法和蚁群算法已经广泛地应用于各类最短路径问题的求解，但这类基于智能控制的算法还没有形成系统的、成熟的算法理论体系，提高搜索速度，克服过早收敛仍然是算法研究的方向。