高 岚
（吉林工程技术师范学院信息工程学院，吉林 长春 130052）
【摘 要】本文通过对比求解最短路径问题的Dijkstra算法和Floyd算法的设计思想、求解过程和应用实例，讨论了两种算法的特点及适用领域。
教育期刊网 http://www.jyqkw.com
关键词 最短路径问题；Dijkstra算法；Floyd算法
作者简介：高岚（1979—），女，吉林长春人，硕士，吉林工程技术师范学院信息工程学院，讲师，主要从事软件工程教学研究。
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算法可求出该网点布局的最佳中转站。
由计算可知，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算法。
5 结束语
本文通过对比两种求解最短路径算法的设计思想、求解过程、应用实例，讨论了算法的特点及适用领域。了解算法求解问题的差异，针对不同类型问题采取对应的求解算法，将大大提升解决问题的效率，对实际生产生活起到重要作用。
教育期刊网 http://www.jyqkw.com
参考文献
［１］辛建亭,胡萍.图论在通讯网中的应用[J].2009,3.
［２］凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009(4):39-45.
［３］邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008(12):511-512.
［４］徐凤生.求最短路径的新算法[J].计算机工程与科学,2006,2.
［５］殷剑宏,吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2005.
［6］陈玉华.浅谈图论在现实生活中的应用[J].云南省教育学院学报,2004.
［７］王燕,蒋笑梅.配送中心全程规划[M].北京:机械工业出版社,2004.
［８］项荣武,刘艳杰,胡忠盛.图论中最短路径问题的解法[J].沈阳航空工业学院学报,2004.
［责任编辑：汤静］
