周志进

(贵阳学院 贵州贵阳 550005)

最短路径算法就是用于计算一个节点到其他节点的最短路径问题，一般是指确定起点的最短路径问题，求起始节点到某一终点的最短路径问题，也常用于已知起点和终点，求解两节点之间的最短路径。

1 MATLAB程序概述

MATLAB 是由美国MathWorks 公司出品的数学软件，MATLAB 意为矩阵工程，将用于一维、二维与三维数值积分的函数进行了统一，并经过基本数学和内插函数的辅助，提供数值分析、矩阵计算等诸多功能，为应用数学、工程设计和数值计算提供全方位的解决方案，很大程度上摆脱了传统程序设计语言的编辑模式。其高效的数值及符号计算功能，可以帮助用户快速处理繁杂的数学运算问题，具备的图形处理功能可以实现计算结果和编程的可视化。MATLAB本身是一个高级的矩阵语言，包括诸多算法、控制语句、函数等面向基本对象或问题的应用程序[1]。比如：在最短路径计算中可以利用矩阵运算和线性方程组的求解或是数据的统计分析来优化相关问题。

2 基于MATLAB的4种最短路径算法

2.1 Dijkstra算法

Dijkstra（迪杰斯特拉）算法是最经典的单源最短路径算法，也就是用于计算一个节点到其他所有节点最短路径的算法。Dijkstra算法采用贪心算法策略，每次遍历与起点距离最近且未访问过的节点，直至扩展到终点。该算法类似于Prim（普里穆）算法在单个节点源中搜索最小生成树，不过Dijkstra算法要求图中不存在负权边[2]。首先假设一个辅助数组，即一个带权的有向图G，数组中起始点v到某一节点的最短路径在算法执行过程中便会算法，但需要注意的是，这个值在计算过程中是不断逼近最终结果的，并不确定就等于最短路径距离。按照最短路径长度的递增次序，依次向节点中加入未确定最短路径的顶点s，不断寻找下一条长度最短的路径，也就是v至s的最短路径，当v到s中各顶点的最短路径长度小于等于v到其余已确定最短路径的节点时，便可认为s到v的距离就是最短路径长度，而且v到顶点s，只包括s中顶点为中间点的最短路径[3]。

2.2 Floyd算法

基于MATLAB 的Floyd-Warshall 算法（简称Floyd算法）也是一种著名的解决任意两点间最短路径的算法，Floyd算法是利用插点的方式在给定的加权图上计算多源点的最短路径算法，从本质上讲Floyd算法是一个动态规划算法。在动态规划算法中，最为关键也是核心理念的就是对于状态的定义，这是因为Floyd算法的单个执行将找到所有顶点之间的最短路径长度，并通过对算法的简单修改来重建路径，以此验证加权图中所有顶点之间的最短路径。以d[k][i][j]可以定位为例，在使用1至k号节点时，计算点i到点j之间的最短路径长度。在加权图中有n个点，从1 到n。k则变为动态规划算法的松弛操作，也就是描述从起点v到s的最短路径上权值的上界，也被称作最短路径估计，通过d[1][i][j]表示只使用1 点作为中间媒介，点i到点j的最短路径长度，以此定义状态，便可构建动态转移方程。动态转移就是在加权图上d[k][i][j]由1 至n转移到1 至k的一种状态转移表示，对这个状态进行动态转移，且有两种情况，i到j最短路径不经过k；i到j最短路径经过k。可以得出基于Floyd算法的动态转移方程：

式中，d[n][i][j]为加权图中所有顶点之间的最短路径长度；k、n皆为顶点；而且要注意Floyd算法虽然是一种可以在具有正负边缘权重加权图中找到最短路径的算法，但是并没有负周期，这就表示动态转移方程应当在不使用任何点的情况下，满足两点之间最短路径的长度的边界条件。这样就可以得出Floyd算法代码：

动态规划算法中都具有利用滚动数组的方式减少算法的空间复杂度，以便更快速地求得最优解，常见的Floyd 算法也都是采用二维数组表示状态。动态转移方程在隐藏阶段索引后就变为：

证明了在第k-1阶段和第k阶段，点i和点k之间的最短路径长度是不变的，也可以说明在第k阶段到第k-1阶段计算中，点k和点j之间的最短路径长度不变。上一阶段的值可以放心用于计算第k阶段时d[i][j]的值。

2.3 Bellman-Ford算法

Bellman-Ford算法相比较上述两种算法可以计算存在负权边的情况，进行n-1 次更新来找到所有节点的最短路径长度。虽然Bellman-Ford 算法与Dijkstra算法有些类似，都可以确定一个节点的最短路径。但不同的是，Bellman-Ford 算法并不知道具体哪个阶段的最短路径确定了，只能知道比上次计算多确定一个，这样进行n-1 次更新后才能确定所有节点的最短路径。算法原理是从已知节点连到其余节点的所有边中的最小边在更新后就是其余节点的最短距离，进而知道一个可确定的最短距离节点，无所谓它具体是哪个节点。Bellman-Ford 算法的优势在于可以用来判断是否存在负环，在不存在负环情况下，进行n-1次更新后便能确定每个节点的最短距离，再用所有边更新一次依然不会改变结果。但如果存在负环，更新一次会改变结果，造成这种情况的原因就是之前假设起点的最短距离是确定的且最短的，而在负环情况下，这个假设不再成立。Bellman-Ford算法的代码表示为：

从代码实现的复杂性就可以看出Bellman-Ford算法的效率并不高。当前如果没有存在负环基本不会采用此算法，而且下述的SPFA算法也是对Bellman-Ford算法的一种优化。

2.4 SPFA算法

SPFA算法主要应用于给定的加权图存在负权边，这种情况下无法运用Dijkstra 算法和Floyd 算法，而Bellman-Ford 算法的复杂度过高。因此，SPFA 算法成为可选的方式。首先，需要约定加权图基本存在负权边也不能存在负权回路，保证最短路径一定存在。虽然可以在执行该算法前做一次拓扑排序，来判断该加权图是否存在负权回路，但这与算法的关系不大，因此不深入分析[4]。SPFA算法的本质是动态逼近法，通过假设一个节点队列来不断更新队列中的首尾节点，在首位节点进入队列后进行松弛操作，如果该节点指向最短路径距离则进行调整，若指向的节点不在队列中，则将该节点加入队列，其中最短路径在队列计算中为估计值，随着队列的不断更迭进行调整从而不断逼近最短距离长度，如此循环直至队列中不存在节点，便能够得到节点之间的最短路径长度。而SPFA算法无法处理带有负权回路的图的原因，就是在某个节点进入队列的次数超过n次，导致队列一直无法计算出经过该节点的最短路径。SPFA算法是Bellman-Ford算法的一种队列实现表示，减少了不必要的冗余计算，原理就是利用队列中的点与所有与其相邻的点进行松弛，不断进行反复迭代来确定最短路径。SPFA算法的代码表示为：

SFPA算法有两个优化算法，为SLF策略和LLL策略，SLF 策略设要加入的节点是j，队首节点为i，若dist(i)＞dist(j)，则将j插入队首，否则插入队尾。简单明了，可使算法计算速度提高10%。而LLL策略设队首节点为i，队列中所有dist 值的平均值为x，若dist(i)＞x则将i插入队尾，查找下一元素，直到某dist(i)≤x，则对i进行松弛操作。SLF+LLL 可大幅提高SFPA 算法的效率。不过在实际应用中，SFPA 算法的时间效率并不稳定，若出现计算时间很长的情况，可采用更为稳定的Dijkstra算法来计算最短路径长度[5]。

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

在实际生活中各类基站的分布需要经过实地勘探、测量与分析才能绘制出基本的图形和方案，根据不同基站节点位置与传输距离，筛选出较短的间距。比如换热站、通信基站等，适宜的间距可以最大程度减少资源传输的浪费问题。根据实际基站模型简化，再将应用图论简化为实际基站分布，便可将基站简化为数个节点，确定一个起始点后，通过基于MATLAB的最短路径算法来规划出基站分布的最短间距，并利用MATLAB 程序绘制出基站分布图，全面表示基站节点之间的距离。特别是很多基站位于城市之中，需要从多条支路方案中筛选出距离相对更近的路线，便可以通过基于MATLAB的Dijkstra算法确定最短路径，有效降低基站建设和运营成本，从根本上解决运作保障和传输距离之间的协调问题[6]。

4 结语

通过分析基于MATLAB的最短路径算法，可以得到基于MATLAB的不同路径算法在最短路径长度计算中的基本原理和代码实现情况，并通过最短路径算法的实际应用，了解到最短路径算法有着良好运用效果，有助于解决各种最优距离、最短距离问题，具有较高的实用性。