最短路径算法及其在路径规划中的应用

1、最短路径算法及其路径规划中的应用摘要：这篇文章把徒步运动的路径规划问题转化为求解图中任意两点间的最短路 径问题，进而针对此问题介绍了 Floyd算法，对该算法的时间花费进行分析，并 介绍了在实际问题中如何灵活运用该算法解决路径决策中遇到的问题。关键词：路径规划、最短路径、决策、Floyd算法将实际地图的转化为有向图在策划一次徒步旅行时，设计正确的旅行的线路特别重要，首先我们必须先 要得到那个地区的地图，以便进行后续的线路规划。当我们拿到某一地区的地图 时，我们可以把地图上的每一条线路用线段表示，用顶点表示地图上的岔路口， 即多条线段的交点，这样就形成了一个由点和线段组成的图。我们可以在每条线

2、段上标上数字，表示两点之间的实际距离，或者表示通过这条路径所需的时间。 当然，如果两点之间没有线段相连，我们可以认为距离为无穷大，用8表示。有 时候某些线路是单向的，即只能从一个方向到另一个方向，不能逆行。这种情况 在具体的路径设计中非常常见，比如，在繁华的都市内会有一些单行道，在山区 景点中，常会出现一些上山索道，这些都是单向线路的常见例子。有时候，沿某 条线路的两个方向所需的时间不同，这种例子更为常见，比如上山与下山，顺风 与逆风等等。对于这两种情况，我们可以在表示路径的线段上加上箭头表示该路 径的方向，形成有向图。比如，在右图所示的有向图中，从点V1直接 到达v2的距离为8，而从v2到v

3、1的距离为3。 从点v1到V0的距离为5，而从V0到v1的距离 为8。这种带有箭头的有向图，比不带箭头的无 向图能够表示更一般的情形，可以说无向图只是 有向图的一种特殊情况。如果我们知道任意两点间的最短路径，这对 我们进行路径规划将会有很大的帮助，但当地图 较为复杂时，凭直觉估计最短路径的方法往往不 可靠，这时就必须借助计算机的强大计算能力，寻找最短路径。下面，我们就以 这种有向图为工具，来探究寻找最短路径的方法。Floyd算法假设在一个景区中有n个景点，作为一个旅行团的领队，必需要知道这n 个景点中任意两个景点之间的最短路径，这时，我们可以使用Floyd算法。首先我们对这n个景点编号为1,2

4、,3.n。然后可以用一个n*n的方阵来存储 任意两点间的最短路径，比如方阵中第i行第j列的元素表示从第i个景点出发， 到第j个景点的最短路径长度，记为dij。同样，我们用一个三维数组aijk （可以想象成一个立方体），表示从第i个景点出发，允许途中经过编号不大于k 的景点，最终到达第j个景点的路径长度。比如，a124表示从一号景点出发 到二号景点的最短路径长度，但必须满足途中只允许经过第一、二、三、四号景 点（不是每个景点必须都经过），而不得经过其他景点。特别的，aij0表示景 点i和j的直接距离（即不经过其他任何点的距离），这些值都可以从地图上直接 读出。aijn则表示，从第i个景点出发，经

5、过1、2.n号景点，到达第j个景 点的路径长度，我们发现这个长度即为从i到j的总的最短路径长度，即dij=aijn。所以，现在问题就转化为计算aijn的值。对于任意的景点i和j，我们都可以很容易从图中得到aij0的值，即为i， j两点之间的线段长度。那么，如何根据aij0来求aijn的值呢？我们可以 用递推法，即先根据aij0求出aij1,再求aij2依次类推，最终求 出aijn。现在问题转化为如何用aijk的值来求aijk+1的值。第一种情况不经过景点k 最短距离aijk其实，考虑从景点i出发，允许途中经过景点1,2,3.k+1，最终到达景点j的 所有路径，我们可以把它们分为两个部分，一种为

6、途中没有经过第k+1个景点， 一种是途中经过了第k+1个景点。对于前一种情况，因为没有经过第k个景点， 它能够达到的最短路径我们已经知道，为aijk。对于后一种情况，我们可以 把景点k+1提出来。该路径即分为从i到k+1，再从k+1到j，而且由于我们已 经把第k+1个景点提取出来，所以从i到k+1的过程和从k+1到j的过程都不允 许再经过景点k+1 （同一个点如果经过两次则必然不是最短路径），即只能经过 编号小于k+1的点。所以从i到k+1的最短距离为aik+1k，从k+1到j的最 短路径为ak+1jk，所以，对于这种情况，从i到j的最短路径为 aik+1k+ak+1jk。我们对两种情况下的最

7、短路径进行比较，就可以得出 aijk+1的值，即为 aijk与 aik+1k+ak+1jk的最小值。第二种情况经过景点k最短距离 aik+1k+ak+1jk算法的时间分析我们利用递推法逐步求出aij1,aijaijn,最终得到任意两点i, j之间的最短路径长度。而aijk是一个三维数组，共有n*n*n=n3个不同元素， 我们求出了每个元素的值，所以至少需要进行n3次计算，当n较大时，这样的 计算量不能忽视。比如一般计算机每秒钟可以进行109,即十亿次计算，这样也 只能求出一千个点中两两之间的最短路径。当然，在一般的路线规划问题中，景 点数最多也不过数十个，这种算法是完全可以满足要求的。在进行实

8、际的路径规划中，我们有时候并不一定需要知道任意两个点之间的 最短距离，而只需要知道某些点之间的最短距离，这样一来，通过Floyd算法， 我们就得到了很多实际上不需要的冗余结果，这必然导致运算速度的减缓。实际 是，如果只需要求给定的某两点之间的最短距离，我们就不会使用该算法，而是 利用Dijkstra算法，这样只需要进行n2次计算，就可以得到结果。算法的应用Floyd算法不仅可以求出最短路径的长度，如果在计算过程中进行简单的标 记，就可以让计算机输出具体的路径方案。现在的很多路径规划软件实际上都是 利用了这一算法。如果在连接两点的线段上标记的不是两点间的距离，而是所需的时间，那么 就可以算出任意两点之间所需的最短时间。当一个地方的地形表较复杂时，最短 路径和时间就显得不那么重要，我们必须要结合当地的地形、天气等因素，设计 一条坡度较缓，树木不那么密集，危险性不高，路面状况较好同时兼顾所需时间 和最短距离的道路。这些，我们都可以通过Floyd算法完成。对于每一条路径，我们可以测出它的长度、估算出所需时间，同时考虑这条 路的难度系数和危险系数，当然，我们还可以考虑天气、风向、周围环境等因素， 给每条路一个综合全面的评价，把它数字化，满足数字越