【运筹优化】最短路算法之Floyd算法 + Java代码实现
一、Floyd算法简介
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
在计算机科学中，Floyd-Warshall算法是一种在具有正或负边缘权重（但没有负周期）的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。
二、Floyd算法思想
2.1 路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵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);
2.2 状态转移方程
其状态转移方程如下： 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算法 java代码
@Data
public class Floyd {
// 距离矩阵
double[][] distance;
/**
* @param distance
* @Description 构造函数
* @Author WSKH
*/
public Floyd(double[][] distance) {
this.distance = distance;
}
/**
* @Description 进行求解
* @Author WSKH
*/
public void solve() throws IOException, ClassNotFoundException {
double[][] cloneDistance = copy2DArr(distance);
// 中间点
for (int i = 0; i < distance.length; i++) {
// 起点
for (int j = 0; j < distance.length; j++) {
// 终点
for (int k = 0; k < distance.length; k++) {
// 起点不等于中间点 and 中间点不等于终点
if (i != j && j != k) {
cloneDistance[j][k] = Math.min(cloneDistance[j][k],cloneDistance[i][j]+cloneDistance[j][k]);
}
}
}
}
// 输出结果
for (double[] doubles : cloneDistance) {
System.out.println(Arrays.toString(doubles));
}
}
private double[][] copy2DArr(double[][] distance) {
double[][] arr = new double[distance.length][distance[0].length];
for (int i = 0; i < arr.length; i++) {
arr[i] = distance[i].clone();
}
return arr;
}
}
四、测试
public class Test {
public static void main(String[] args) throws IOException, ClassNotFoundException {
double[][] distance = new double[][]{
{0,6,13,20,10,9,3,4,4},
{6,0,7,14,4,6,3,2,10},
{13,7,0,9,11,13,10,9,17},
{20,14,9,0,10,12,17,16,24},
{10,4,11,10,0,2,7,6,14},
{9,6,13,12,2,0,6,6,13},
{3,3,10,17,7,6,0,1,7},
{4,2,9,16,6,6,1,0,8},
{4,10,17,24,14,13,7,8,0}
};
new Floyd(distance).solve();
}
}
控制台输出：
[0.0, 6.0, 13.0, 20.0, 10.0, 9.0, 3.0, 4.0, 4.0]
[6.0, 0.0, 7.0, 14.0, 4.0, 6.0, 3.0, 2.0, 10.0]
[13.0, 7.0, 0.0, 9.0, 11.0, 13.0, 10.0, 9.0, 17.0]
[20.0, 14.0, 9.0, 0.0, 10.0, 12.0, 17.0, 16.0, 24.0]
[10.0, 4.0, 11.0, 10.0, 0.0, 2.0, 7.0, 6.0, 14.0]
[9.0, 6.0, 13.0, 12.0, 2.0, 0.0, 6.0, 6.0, 13.0]
[3.0, 3.0, 10.0, 17.0, 7.0, 6.0, 0.0, 1.0, 7.0]
[4.0, 2.0, 9.0, 16.0, 6.0, 6.0, 1.0, 0.0, 8.0]
[4.0, 10.0, 17.0, 24.0, 14.0, 13.0, 7.0, 8.0, 0.0]
五、优缺点分析
Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。
此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。