基于MATLAB的最短路径算法研究

①唐巧玲　②郑晓敏

一、绪论

最短路径问题因为其问题的普遍性，以及应用的实际性，不仅是数据结构的热点问题，也是数学信息学科、计算机学科、地理信息学科等学科的一个研究热点。由于科学技术的不断进步，使得应用数学中的图论与计算机算法与结构结合，出现了不一样的较短路径算法。最短路径即点到点之间的路径是最短的，因此可以看作计算机中的图片问题，即如何从图片上找到两个顶点的路径所经过的最短路径，而最短路径算法也就提供了如何寻找某两点之间最短距离的思路。

二、最短路径算法介绍

最短路径是图论与复杂网络分析中的一个经典问题。最短路径算法则是将所需要求的问题，转化为图论问题，并通过相关的操作，最终得到问题所求的最短路径的过程。本文采用一个由n个节点和m条边组成的图G（V，E）作为路径图，V集合存放G中所有的顶点，E集合存放G中所有的边，将顶点之间存在的边的权值设为w。

（一）最短路径的基本概念

最短路径问题是求由源点到达图中其他任一顶点的最短路径，即在由节点构成的路径图中，找出一条经过路径的权值总和最短的路径。在图论研究中，假设将设置为源点，终点设为V_j，则寻找最短路径的形式有以下几种：

1、源点确定，求最短路径。

2、终点确定，求最短路径则需要进行讨论分析;若在无向图中，终点确定可以转化为顶点确定的问题来进行解决;若在有向图中，就需要将路径方向反转，通过找起点来确定此时终点确定下来的最短路径。

3、源点终点都确定，直接进行寻找两点之间的最短路径。

4、全局最短路径，可以运用以上三种方法，求出任意两点之间的最短路径。

（二）Diikstra算法

Diikstra算法运用贪心策略的思想。首先，每次找到离源点最近的一个顶点，记录源点到此顶点的距离，并标记此顶点，接着查找未标记顶点到源点的距离，与通过标记点经过的距离进行比较，最终找到源点与其他各个顶点之间的最短路径。

Diikstra算法的具體步骤如下：

1、将图中所有顶点分为两类，分别存放在P和Q两个集合中。其中P集合存放的顶点是已经求出了与源点存在最短路径的顶点;Q集合存放的是未被求出与源点存在最短路径的顶点，同时设置源点到自身之间的距离为0，源点与其他顶点之间存在直接边，则设置源点到此顶点直接距离为该边权值V，而把源点与顶点之间不存在直达边的距离设置为∞;

2、已知源点到自身的距离为0是默认的，故直接将源点放入P中;

3、在Q集合寻找距离源点最近的顶点V_i，并将顶点V_i放入P中，表示以求得源点到顶点V_i之间的最短路径;

4、重复第3步，将Q集合中的点遍历完毕，算法结束，源点到图中所有顶点之间的最短路径也查找完毕。

（三）Floyd算法

三、最短路径算法研究

本文使用了Dijkstra算法和Floyd算法，针对具体问题建立模型，并通过两种算法的不同算法结果来进行分析比较。

（一）问题分析

某公司在六个城市有分公司，记为ci，则从ci到cj的直接航程票价如表3.1.1所示（∞表示无直接航路），要求找到一个城市到其他城市间票价最便宜的路线图。

表1 某公司总航线表

根据表1得到某公司总航线图如图1所示，其中权值代表ci到cj的直接航程票价。因此上述问题就可转换成图论研究中的最短路径问题。因为起点和终点都不确定，则需对全局最短路径进行求解。

图1 某公司总航线图

（二）模型的建立和求解

通过问题分析，本文基于MATLAB平台，使用Dijkstra算法和Floyd算法对上述全局最短路径问题进行求解，从而得到一个城市到另一个城市之间的最便宜票价。

1、Dijkstra算法

假设以第一个城市c1为源点，求源点c1到除源点外的顶点的最短路径，首先用矩阵存放各边权值的邻接矩阵，行向量pb、index₁、index₂、d分别用来存放标号信息、标号顺序、标号顶点索引、最短通路的值。

根据上述设置和数据求第一个城市到其他城市的最短路径的核心代码如下：

while sum（pb）

m=find（pb==0）：

d（m）=min（d（m），d（temp）+a（temp，m））：

tmpb=find（d（m）==min（d（m）））：

temp=m（tmpb（1））：

pb（temp）=1;

indexl=[index1，temp];

index=index1（find（d（index1）==d（temp）-a（temp，index1）））：

if length（index）>=2

index=index（1）：

end

index2（temp）=index：

end

由此，可得出运用Dijkstra算法求解出的c1至其他城市的最短路径如图所示。

图2 Dijkstra算法实例cl源点最短路径图

2、Floyd算法

首先初始化数据，设置无穷大值M=100000，矩阵f存放表3.1.1的数据值，一个与矩阵f同等大小的全零矩阵path，用于存放任意两个顶点最短路径的中间节点k。

求任意两城市之间的最短路径的核心代码如下：

四、仿真及结果对比分析

（一）结果分析

通过matlab仿真平台，以c1为源点，使用Uijkstra算法和Floyd算法可以得到如图3和图4的结果，从图中可知Dijkstra算法得到的是单原点到其他顶点的数据，而Floyd算法最后得出的path表格可以查询任意两点之间的节点，从而得到任意两点间的最短路径。

图3 Dijkstra算法最短路径图

图4 Floyd算法path图

相对于Diikstra算法，Floyd算法更加全面与简洁，效率比n次的Dijkstra算法要高，因此Floyd算法更适用于多源最短路径，可以算出任意两个顶点之间的最短距离。

（二）两种算法比较

首先从算法思想的角度出发，Dijkstra算法是在寻找最短路径时进行串行的寻找模式，虽然做到了局部最优，但不能实现整体最短，除此之外Diikstra算法的代码冗长繁瑣，效率较低;而Floyd算法较简洁，效率高。

在执行上，Diikstra算法会进行两次遍历，一是先将所有与源点相连的点作为中间点遍历;二是在中间点的基础上对相邻且未标记的点进行遍历。所以Dijkstra算法的时间复杂度和空间复杂度都是O（n*n）;Floyd算法则经过了第一次对中间点k遍历，第二次对源点i遍历，最后对终点j的三次遍历，时间复杂度是O（n*n*n）。因此Floyd算法时间复杂度高，不适合计算大量数据。

五、结论

本文完整描述了Dijkstra和Floyd两种最短路径算法的算法思想和实现步骤，并针对同一实际问题使用matlab平台对这两种算法进行了仿真。通过对仿真结果的对比分析可得，Floyd算法相较于Diikstra算法实现更简单，效率更高，因此解决此类问题会更偏向于Floyd算法，但其时间复杂度也更高，不适于计算大量数据的模型。诸如此类的最短距离问题不仅仅适用于本文的例子，还可以运用到其他很多地方。但本文提出的方法对解决此类问题只有一定的参考作用，在实际问题中需要依据不同的情况和要求，对算法进行正确的选择和适当的调整。