第三章 路径分析算法——基于Floyd算法的路径分析

Floyd算法模高是一种用于在已知给定的加权图中求多源点之间最短路径的算法。它于Diskstra算法类似，不同点在于Diskstra计算的是单源点之间的最短路径。Floyd算法是在数学建模领域和日常工作中使用频率较高的路径分析算法。

Floyd作为一种典型的求多源最短路径悄漏问题的算法，是解决任意两个点之间最短路径的旦运尺算法，它的思想是基于动态规划的思想。

见——第一章 算法基础——基础算法分析类型。

Floyd的核心思想也是基于动态规划的理论，过程也比较简单。

设 表示为i点到j点过程中以(1…k)集合中的节点为中间节点的最短路径长度，则：

（1）若最短路径经过点k，则 = +

（2）若最短路径不经过点k，则 = 。

于是 = .

Floyd算法的时间复杂度为 ，空间复杂度为 。

最短路径的算法主要有三种：floyd算法、Dijkstra算法、Bellman-Ford(贝尔曼-福特)

一、floyd算法

基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) <Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

二、Dijkstra算法

算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中尘喊（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

执行过程如图所示：

三、Bellman-Ford(贝尔曼-福特)

算法滑带的流程如下：

给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，

1.数组Distant[i]记录从源点s到派让野顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；

2.以下 *** 作循环执行至多n-1次，n为顶点数： 

对于每一条边e(u, v)，如果Distant[u] + w(u, v) <Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 

若上述 *** 作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

3.为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) <Distant[v]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

matlab中filepath是文件路径的意思；

MATLAB用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式缺神环境，主要包括MATLAB和Simulink两大部分。

MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常冲敏用的形式十分相似，故用散扮枝MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。

在新的版本中也加入了对C，FORTRAN，C++，JAVA的支持。

---