数据结构最短路径算法及其应用

韩加军

摘 要： 最短路径算法研究是计算机科学研究的热门话题，不仅具有重要的理论意义，而且具有重要的实用价值。最短路径问题可以引申为最快路径问题、最低费用问题等，但它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra和Floyd算法是目前最短路径问题采用的理论基础。本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际问题。

关键词： 最短路径 Dijkstra算法 Floyd算法 图论

最短路径，就是在所有路径中找到一条距离最短的路径，而我们所说的最短路径不仅指地理意义的距离最短，而且可以引申到其他度量，如时间、费用、路线容量。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做最优路径问题。最短路径问题在交通网络结构的分析，交通运输路线的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等方面，都有直接应用的价值。最短路径问题在实际中常用于汽车导航系统及各种应急系统等这些系统，一般要求计算出到出事地点的最佳路线的时间应该在1s到3s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。经典图论与不断发展完善的计算机数据结构及算法的有效结合使新的最短路径算法不断涌现。

一、图论基本概念

1.图的定义。图（graph）是一种较线性表和树更为复杂的数据结构，图与线性表和树的结构区别表现在结点之间的关系上，线性表中的每个结点（除首尾结点外）都有一个前驱结点和一个后继结点，结点与结点之间的关系是一对一的关系；树上的每个结点都有一个父结点（根结点除外）和一个或多个孩子结点（叶子结点除外），结点与结点的关系是一对多的关系；而图中结点之间的关系是多对多的关系，结点与结点之间的连接是任意的，每对结点间可以有连接也可以没有连接。

2.图的存储结构。除了存储图中各个顶点本身的信息外，还要存储顶点与顶点之间的所有关系。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。

二、最短路径问题

所谓最短路径即从图G中某对顶点Vi和Vj（i≠j）之间的所有路径中选出权值之和最短的一条路径作为顶点Vi到顶点Vj的最短路径。其中边的权值可多种，如路途、费用、耗时等，也可以同时存在多种权值，根据给定的比例，算出边的综合权值。

1.最短路径。在一个无权的图中，若从一个顶点到另一个顶点存在一条路径，则称该路径长度为该路径上经过的边的数目，等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在多条路径，每条路径上经过的边数不同，即长度不同，把长度最短的那条叫做最短路径。

2.最短路径算法。求图中最短路径有两方面问题：求图中某一顶点到其余各顶点的最短路径与求图中每一对顶点之间的最短路径。它们分别有Dijkstra算法和Floyd算法。

2.1Dijkstra算法。Dijkstra算法又称为标号法，是用于求解单源点最短路径的实用算法，至今仍然被公认为是解决从固定点出发到网络中的任意顶点的最短路径问题的较好方法之一。基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中，V为网中所有顶点集合。按最短路径长度递增的顺序逐个用V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。

2.2Floyd算法。Floyd算法能够求得任意顶点之间的最短路径。基本思想是任意2个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点vk，然后将vi到vj间的已知最短路径与插入顶点vk作为中间顶点时可能产生的vi到vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出N个矩阵D（1），D（2）…D（n），当所有顶点均作为任意 2个顶点vi到vj中间顶点时得到的最后的带权邻接矩阵D（n）就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。

三、 应用举例

1.Dijkstra算法在公交网络中的应用。在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径应该怎样实现呢？针对这个问题采用图论中最短路径思想进行了思考和研究，并采用Dijkstra算法实现搜寻计算操作和过程。

（1）实际问题描述。公交网络中最短路径问题可以描述为从某起始站点S出发到达目的站点E，其中S和E之间可行的线路往往不只一条，而是有很多条，那么这么多可行线路中哪一条是最短的呢？这里“最短”指实际走过的路程最短，或指在不计算公交换乘花费时间和公车保持匀速行驶的前提下，能够以最短时间到达目的地中的“最短”。要求解这个问题如果不考虑其他各方面的复杂因素，就可以看成一个简单的最短路径问题。

（2）数学模型建立。起始站点、目的站点及所有可行路径和中间站点构成的交通网络，可以抽象为一个图状的数据模型——有向带权图记为G=（V，E，L），其中V表示所有站点的集合，假设共有N个站点；E表示所有直接通路或直通边的集合，假设共有M条直通边，注意，在实际应用中，这里的边是有方向性的，边的方向表示该直接通路的可行方向；L表示每条直接通路对应的边权集合，即每条直通边对应的距离值或时间开销等。

（3） 实际问题抽象化。经过上述分析和建模，实际最短路径问题可抽象为有向带权图中两顶点之间的最短路径问题。

四、结语

若寻找从起始点到其他所有顶点的最短路径，按照Dijkstra算法则最多需要经过N-1步的搜寻计算操作（N表示G中的顶点个数）。在实际应用中，Dijkstra算法称为单源点最短路径算法。事实上，Dijkstra最短路径算法除了可以用在公交网络上之外，还可以用在现实生活的很多方面，如邮政线路、物流线路、管道布线等，我们还可以不断将其推广应用于更多方面，从而使数学与计算机科学能够更充分地为人类服务。

参考文献：

[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2002.

[2]李春葆，曾慧，张植民.数据结构程序设计题典[M].北京：清华大学出版社，2002.

[3]张永，李睿，年福忠.算法与数据结构[M].北京：国防工业出版社，2008.

[4]刘玉龙.数据结构与算法实用教程[M].北京：电子工业出版社，2007.

[5]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2004.

[6]曹晓东，原旭.离散数学及算法[M].北京：机械工业出版社，2007.