Floyd算法概述
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中任意两顶点之间最短路径的算法，与 Dijkstra算法类似都是属于贪心算法。
基本思路：首先定义两个数组，数组D[i][j]记录顶点i到顶点j的最短距离，数组prior[i][j]记录i到j最短距离经过的一个顶点。在顶点i，j之间找到一个中间点m，若i到m的距离加m到j的距离小于原来i到j的距离则更新D[i][j],并将prior[i][j]更新为m，m用所有顶点一个一个试，最终得到i到j的最短距离和最短路径。对任意两个顶点进行上述操作，得到任意两个顶点的最短距离和最短路径所要经过的一个中间顶点，从中间顶点到起始顶点也有一个最短路径的中间顶点，依次类推， 通过任一局部的最短路径达到整体路径最短.
Floyd算法不适用于负权回路，因为负权回路可以不断循环，没有最小值。
for (k = 0; k < n; k++) { for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (D[i][k] + D[k][j] < D[i][j]) { D[i][j] = D[i][k] + D[k][j]; prior[i][j] = prior[k][j]; } }
算法步骤
- 定义两个矩阵,D[i][j]记录顶点i与j的最短距离，prior[j]记录j的前一个顶点
- 初始化矩阵Dij为顶点i与j的直通距离，若不能直通则为infinity，矩阵priorij为i，j顶点最短路径经过的中间顶点，即j的前一个顶点，初始时i，j顶点之间没有中间顶点，若i，j直通则j的前一个顶点priorij为i，否则j没有前一个顶点，priorij记为－1。
- 构造三层循环，最外层循环从第一个顶点产生中间顶点k，第二层循环从第一个顶点开始产生起始点i，最后一层循环从第一个顶点开始产生终点j，依次将中间顶点加入所有任意两顶点i，j之间，比较Dik+Dkj与原来Dij的大小，若Dij较大，则加入的中间顶点k使顶点i到j的距离更近，更新Dij＝Dik+Dkj，priorij＝k，重复上述操作，直到外层循环结束，即任意两点之间试过所有中间顶点，找到最短路径。
图解
画表好麻烦，有时间再补上代码：
/** Floyd算法
* @g 邻接矩阵表示的图
* @D D[i][j] 记录i到j的SP长度,
* @prior prior[i]记录以i为源点至各点的SP（等同Dijkstra算法中,i为源点SP问题的prior）
* 动态规划,分阶段决策,迭代处理D:
* 初始,D为邻接矩阵 (D[i][j]:不经过任何结点i至j的SP长度)
* 第k(k=0,1...n-1)次决策,允许路径经过编号不超过k的顶点 (D[i][j]:i至j的SP可经0...k号顶点的SP长度）
* 第n-1次(n:顶点数)决策,D[i][j]允许经过任何顶点的SP,即为解
*/
void Floyd (MGraph g, float D[][N], int prior[][N])
{
int i,j,k,n=g.vexnum;
/**矩阵D与prior初始化*/
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
D[i][j] = g.arcs[i][j]; // 初始 D为邻接矩阵
//若i，j可直接连通，则j的前一个结点prior初始化为i，否则为-1
prior[i][j] = (i!=j && D[i][j] < INFINITY )? i: -1;
}
/** n次决策,第k次迭代(k=0...n-1)允许编号k顶点插入路径 */
for (k = 0; k < n; k++) //k为中间顶点
{
for (i = 0; i < n; i++) //以i为起始点
for (j = 0; j < n; j++) //以j为终点
if (D[i][k] + D[k][j] < D[i][j]) // 经过k顶点更短
{
D[i][j] = D[i][k] + D[k][j]; // 更新SP长度
prior[i][j] = prior[k][j]; //更新SP
}
}
}
/** 输出有向网,任意两点间的SP 及其长度
@g 邻接矩阵表示的有向网*/
void Floyd_SP(MGraph g)
{
int n = g.vexnum;
float D[n][N];
int prior[n][N];
int i,j;
Floyd(g,D,prior); // 调用Floyd算法,D存储任意两点间SP长度,prior存储各SP
cout << "任意顶点对的最短路径(SP)长度 矩阵(INF为无限大):" << endl;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if( D[i][j] == INFINITY)
cout << " "<< "INF" ;
else
cout << setw(6) << D[i][j];
}
cout << endl;
}
cout << "\n任意顶点对的最短路径(SP) " << endl;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(i==j || D[i][j] == INFINITY) // i与j不连通,则无输出
continue;
Traceback(g,prior[i],j); // 输出i到j的SP
cout << "\t";
}
cout << endl;
}
}
输出结果：
任意顶点对的最短路径(SP)长度 矩阵(INF为无限大):
0 INF 10 50 30 60
INF 0 5 55 INF 65
INF INF 0 50 INF 60
INF INF INF 0 INF 10
INF INF INF 20 0 30
INF INF INF INF INF 0
任意顶点对的最短路径(SP)
A C A E D A E A E D F
B C B C D B C D F
C D C D F
D F
E D E D F
