最短路径

目录

简介

核心思路

优缺点分析

算法过程

         示例

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

路径矩阵

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 [3] 

从图的带权邻接矩阵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来记录两点间的最短路径。

采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

状态转移方程

其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；

map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。

当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

编辑 语音

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。

缺点：时间复杂度比较高，不适合计算大量数据

 在Floyd算中一般会用到有两个矩阵，一个距离矩阵D，一个路由矩阵R，顾名思义距离矩阵D是用来储存任意两点之间的距离的，而路由矩阵则是用来记录任意两点之间的路径关系。  

Floyd算法的原理是：对于每一对顶点 i 和 j，看看是否存在一个顶点 w 使得从 i 到 w 再到 j 比已知的路径更短。如果是更新它。

把图用邻接矩阵r表示出来，如果从Vi到Vj有路可达，则D[i，j]=d(在矩阵D中为具体的数字)，d表示该路的长度；否则D[i，j]=无穷大（在矩阵D中用“inf“表示）。定义一个矩阵D用来记录所插入点的信息，R[I,j]表示从Vi到Vj需要经过的点，初始化R[i,j]=j（即先默认i到j是通的）。把各个顶点插入图中，比较插点后的距离与原来的距离，假设插入的中间点为k，D[i,j] > D[i,k]+D[k,j] )，此时证明从i点经过k点再到j点比原来的要短，所以此时要更新D[i,j],则D[i,j]=D[I,k]+[k,j],同时此时R[i,j]=k。在R中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

可能有些人对路由矩阵R不是很明白，其实路由矩阵R很好理解，我来举个例子，

比如，要寻找从V5到V1的路径。根据R，假如 R(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果R(5,3)=3，说明V5与V3直接相连，如果R(3,1)=1，说明V3与V1直接相连。

因此，我们在定义路由矩阵R时，先要初始化矩阵（即先默认任意两点是相互相通的），即每列上的数等于该列的列序数。

例：

下面我将用一个简单的例子来说明，下面是一个简单的例子：

问题：求出任意两点间的最短距离及其路径？

我们此时可以写出距离矩阵D和路由矩阵R如下：

这样我们就定义好了距离矩阵和路由矩阵，现在我们再来假设图中任意两点之间都要经V5这个点中转。算出经过中转后的两点之间的距离，然后我们再来判断任意两点之间的最短距离。 （1）先从V5开始，先让V5成为中转点。

V5由V5中转，那么V5到到各个点的距离还是不变。

V4可以经由V5中转，那么这个时候判断一下中转前和中转后的距离大小，将最小距离留存下来如：

V4>V3 经V5中转，原来V4->V3 = inf，经由V5中转之后V4->V5->V3 = 17, 于是V4到V3的最短距离变化为17，更新距离矩阵D(4,3)=17,更新路由矩阵R(4,3) = R(4,5) = 5

V1、V2、V3没有到达V5的路径，所以也就不存在从V5中转的情况，所以V1、V2、V3到各个点的距离还是不变。

这时两个矩阵变化为

（2）再让V4成为中转点。

V5  V1 都没有到达V4的路径，所以也就不存在从V5中转的情况，所以V5 V1 到各个点的距离还是不变。

V2>V5 经V4中转，原来V2->V5 = inf，经由V4中转之后V2->V4->V5 = 15, 于是V2到V5的最短距离变化为15，更新距离矩阵D(2,5)=15,更新路由矩阵R(2,5) = R(2,4) = 4

V3>V2经V4中转，原来V3->V2= inf，经由V4中转之后V3->V4->V2 = 5, 于是V3到V2的最短距离变化为5，更新距离矩阵D(3,2)=5,更新路由矩阵R(3,2) = R(3,4) = 4

V3>V5 经V4中转，原来V3->V5 = 6，经由V4中转之后V3>V4->V5 = 11, 因此V3到V5的最短距离仍为6，不更新。

这时两个矩阵变化为

 (3)同理，让所有的点都成为一次中转点

用Matlab来表示上面的过程，其代码为：

（1）先建立一个.m文件

（3）得出距离矩阵D和路由矩阵R 

（4）怎么通过得出的这两个矩阵看任意一点到任意一点的最短距离及其路径。

从任意一点到任意一点从矩阵d中就很容易看出来了，比如D(2,3)=9,就表示V2到V3的最短距离是9，因此两点的距离从矩阵中很容易看出，我就不过多解释了。

现在我重点来说一下怎么看路由矩阵：

举个例子：v4->V3

从距离矩阵中可以看出V4->V3的最短距离是D(4,3) = 12；根据其路由矩阵我们可以看出：

R(4,3) = 2,表示V4->V3,先经过V2，于是再看R(2,3) = 1,表示还需要再经过V1,于是我们看R(1,3) = 3,这个时候我们发现终于到了V3,所以我们梳理一下，V4->V3的最短路径是：V4->V2->V1->V3。简言之就是固定列，根据路由矩阵在行中跳转，直到跳转到对应的点。

再来个例子：v5->V2

从距离矩阵中可以看出V5->V2的最短距离是D(5,2) = 13；根据其路由矩阵我们可以看出：

R(5,2) = 3,表示V5->V2,先经过V3，于是再看R(3,2) = 4,表示还需要再经过V4,于是我们看R(4,2) = 2,这个时候我们发现终于到了V2,所以V5->V2的最短路径是：V4->V2->V1->V3。