S9-算法-弗洛伊德算法【2020-02-11】
总目录：地址如下看总纲
1、应用场景-最短路径问题
建国时期，史莱村乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄，各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
问：
1、如何计算出G村庄到 其它各个村庄的最短距离?
2、如果从其它点出发到各个点的最短距离又是多少?
image.png
2、弗洛伊德(Floyd)算法介绍
（1）和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。
（2）该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
（3）迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
（4）弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。
3、弗洛伊德算法思路
1、说明：不必，深究
（1）设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径
（2）至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得
2、图解：主要学习方式
核心是两个二维数据：一是初始的各顶点的距离表，二是初始前驱顶点关系表，还有三层循环
image.png
image.png
步骤图：
（1）广度大图
image.png
（2）
image.png
（3）根据三种情况，演变出箭头指向图，为三种情况的变化
（4）
image.png
（5）说明：
情况一:将C-G从N替换为9，因为这样更短
情况二:将C-B从N替换为12,因为距离更短
情况三:将G-B不替换，因为原本不经过A的时候距离才3，经过之后距离为7，更远了，所以不替换
4、代码
public class FloydAlgorithm {
public static void main(String[] args) {
// 测试图是否创建成功
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
// 创建邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
matrix[2] = new int[]{7, N, 0, N, 8, N, N};
matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};
// 创建 Graph 对象
Graph graph = new Graph (vertex.length, matrix, vertex);
// 调用弗洛伊德算法
graph.floyd ();
graph.show ();
}
}
// 构建图
class Graph {
private char[] vertex; // 存放顶点的数组
private int[][] dis; // 保存各个顶点出发到其他顶点的距离（同样也是保留最终结果）
private int[][] pre; // 保存到达目标顶点的前驱顶点
/**
* 构造器
*
* @param length 定义大小
* @param matrix 邻接矩阵
* @param vertex 顶点数组
*/
public Graph(int length, int[][] matrix, char[] vertex) {
this.vertex = vertex;
this.dis = matrix;
this.pre = new int[length][length];
// 初始化 pre 数据，注：存放应是前驱顶点的下标
for (int i = 0; i < length; i++) {
Arrays.fill (pre[i], i);
}
}
// 显示 pre 和 dis 两个二位数组
public void show() {
// 为了便于阅读，进而优化输出
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
for (int k = 0; k < dis.length; k++) {
// 先输出前驱数组 pre 的一行
for (int i = 0; i < dis.length; i++) {
System.out.print (pre[k][i] + " ");
}
// 再输出dis 数组的一行
for (int i = 0; i < dis.length; i++) {
System.out.print ("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ") ");
}
System.out.println ( );
System.out.println ( );
}
}
// 核心：弗洛伊德算法, 比较容易理解，而且容易实现（三层循环）
public void floyd() {
// 变量保持距离
int len = 0;
// 对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G]
for (int k = 0; k < dis.length; k++) {
// 从i顶点开始出发 [A, B, C, D, E, F, G]
for (int i = 0; i < dis.length; i++) {
// 到达j顶点 // [A, B, C, D, E, F, G]
for (int j = 0; j < dis.length; j++) {
// 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
len = dis[i][k] + dis[k][j];
if (len < dis[i][j]) { // 若len小于 dis[i][j]
dis[i][j] = len; // 更新距离
pre[i][j] = pre[k][j]; // 更新前驱顶点
}
}
}
}
}
}
5、仓库坐标
image.png
