浅议求解最短路径问题的两种算法

2015-12-25高岚

科技视界 2015年18期

高岚

（吉林工程技术师范学院信息工程学院，吉林长春 130052）

0 引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交路线网络规划中应用广泛。因此，实际公交线网优化设计中，路径选择算法成为一个重要研究课题，它直接关系到交通网络效率、传输延迟和吞吐量等主要技术性能指标。

早在20世纪初，最短路径这一重要问题就已得到人们的高度重视，当时有许多科学家研究这一问题的求解方法，但直到1959年荷兰计算机科学家Dijkstra（迪加斯特拉）才给出这一问题求解的基本思想，成为一代经典。当时的Dijkstra 提出的这一算法主要解决的是从固定的一点到其他各点的最短路径问题。但实际生活中要求解的可能是任意两点间的最短距离，可采用Floyd（弗洛伊德）算法。本文通过将两种算法进行一些对比讨论，得出关于两种算法效率和适用问题的一些结论。

1 最短路径问题

最短路径问题是图论中的基本问题。在赋权图中，找出两点间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总费用最少。在图论中最典型的两种求最短路径算法分别是Dijkstra 算法和Floyd 算法。

2 Dijkstra 算法

2.1 算法基本思想

每次新扩展一个距离最短的点，更新与其相邻点间距离。当所有边的权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离不会再被改变，因而保证了算法的正确性。根据这个原理，采用Dijkstra 算法求解最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。

2.2 Dijkstra 算法思想在物流配送中的应用

采用图论中的最短路径算法Dijkstra 算法来建立物流配送路径选择模型，主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点时两点间的最短路径，得到的最终的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的物流配送选址位置。

3 Floyd 算法

3.1 算法基本思想

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A＝[a(i，j)]n×n 开始，递归地进行n 次更新，即由矩阵D(0)＝A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i 行j 列元素便是i 号顶点到j 号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path 来记录两点间的最短路径。

3.2 Floyd 算法在选址问题中的应用

某城市考虑建立区域内二次供水中转站。在选址问题中，点表示可供选址，其间连线表示运输费用，其需求点之间运费如图1 所示。在选址中，要求该中转站到其他站点的距离最短，即运输费用最少，通过运用求解最短路径的Floyd 算法可求出该网点布局的最佳中转站。

图1 网络拓扑

由计算可知，a 到其他点的费用和为C(a)＝33，同理C(b)＝27，C(c)＝18，C(d)＝21，C(e)＝33，比较可知c 到其他各点的费用最小。因此本例从经济性考虑，选c 点为中转站最优。

4 讨论

典型的最短路径求解算法Dijkstra 算法和Floyd 算法各有所长。Dijkstra 算法可为任一源节点找出与其它所有节点的最短路径，是目前公认的较好的最短路径算法，但由于它遍历计算的节点很多，所以效率低。Floyd 算法是一种用于寻找给定的加权图中顶点间最短路径的算法，是一种动态规划算法，可以算出任意两个节点之间的最短距离，代码编写简单，但是Floyd 算法计算最短路径时时间复杂比较高，不适合计算大量数据。

综上，求解单源点无负权边最短路径可采用Dijkstra 算法，而求所有点最短路径应用Floyd 算法。对于稀疏图，采用n 次Dijkstra 算法比较出色，对于稠密图，适用Floyd 算法。