数据结构与算法_最短路径之Floyd算法

Dijkstra算法是求源点到其他各个顶点的最短路径，如果求解任意两个顶点的最短路径，则需要以每个顶点为源点，重复调用n次Dijkstra算法。完全没有必要这么麻烦，下面介绍的Floyd算法可以求解任意两个顶点的最短路径。Floyd算法又称为插点法，其算法核心是在顶点i到顶点j之间，插入顶点k，看是否能够缩短i和j之间的距离（松弛操作）。

算法步骤：

1）数据结构。

设置地图的带权邻接矩阵为G.Edge[ ][ ]，即如果从顶点i 到顶点j有边，就让G.Edge[i][j] = <i,j>的权值，否则G.Edge[i][j] = 无穷大；采用两个辅助数组；最短距离数组dist[ i][j]，记录从i 到j顶点的最短路径长度；前驱数组p[i][j],记录从 i 到j顶点的最短路径上j顶点的前驱。

2）初始化。

初始化dist[i][j] = G.Edge[i][j],如果顶底i 到顶点j 有边相连，初始化p[i][j] = i,否则p[i][j] = -1。

3）插点。

其实就是在i,j之间插入顶点k,看是否能够缩短i和j之间距离（松弛操作）。如果dist[i][j] >dist[i][k] +dist[k][j],则dist[i][j] = dist[i][k] + dist[k][j],记录顶点j 的前驱为：p[i][j] = p[k][j]。

一个例子：

1）数据结构：

设置地图的带权邻接矩阵为G.Edge[ ][ ],即如果从顶点i 到顶点j有边，就让G.Edge[i][j] = <i,j>的权值，当 i = j 时， G.Edge[i][j] = 0,否则G.Edge[i][j] = 无穷大。

2）初始化

初始化最短距离数组dist[i][j] = G.Edge[i][j] ;如果顶点i 到 j有边相连，初始化前驱数组p[i][j] =i，否则p[i][j] = -1。初始化后的dist[ ]和p[ ][ ]，如图所示：

3）插点（插顶点0，k=0）

其实就是借点，借东风，大家一起借顶点0更新最短距离。如果dist[i][j] > dist[i][0]+dist[0][j],则dist[i][j] = dist[i][0] + dist[0][j]，记录顶点j的前驱为：

p[i][j] = p[0][j]。

谁可以借顶点0呢？

看顶点0的入边，2--->0，也就是说顶点2可以借0点，更新2到其他顶点的最短距离。（程序中通过穷举所有顶点来判断是否可以借0点）。

dist[2][1]:    dist[2][1] = 5 > dist[2][0] + dist[0][1] = 4,则更新dist[2][1] = 4,p[2][1] = 0;如图所示：

4）插点（插顶点1，k = 1）

大家一起借顶点1更新最短距离。谁可以借顶点1呢？

看顶点1的入点，顶点0、2都可以借1点，更新其到其他顶点的最短距离。

dist[0][2]:    dist[0][2] = 无穷大 > dist[0][1] +dist[1][2] = =10,则更新dist[0][2] = 10,p[0][2] = 1;

5)插点（插顶点2，k=2）

大家一起借顶点2，更新最短距离。从顶点2的入边可知，1，3可以借。

6）插点（插顶点3，k=3）

大家一起借顶点3，更新最短距离。看顶点3的入边，顶点0、1、2都可以借3点。

7）插点结束。

dist[][]数组即为各顶点之间的最短距离，如果想找顶点i 到顶点j的最短路径，可以根据前驱数组p[][]获得。

例如：

1）求1到2的最短路径，首先读取p[1][2] = 3,说明顶点2的前驱为3，继续向前找，读取p[1][3] = 1,说明3的前驱为1，得到1到2的最短路径为1-> 3->2。

2）求1到0的最短路径，首先读取p[1][0] = 2,说明顶点0的前驱为2，继续向前找，读取p[1][2] = 3,说明2的前驱为3，继续向前找，读取p[1][3] =1，得到1到0的最短路径为1->3->2->0。