【Java】我所知道的十大常用算法之费洛伊德算法（最短路径）
前言需求
今天我们学习的是弗洛伊德算法，我们还是从一个场景里引入看看
战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G)
有一名邮差需要你的帮忙:从G点出发，分别把邮件分别送到 A, B, C , D, E, F 六个村庄
问：如何计算出各村庄到其它各个村庄的最短距离?
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
如我们问的是：如何计算出G村庄到 其它各个村庄的最短距离?
那么采用我们之前的方式：迪杰斯特拉算法（路径" title="最短路径">最短路径）
但是我们今天问的是：如何计算出各村庄到其它各个村庄的最短距离?
所以今天我们我们使用新的算法来解决这个问题：弗洛伊德算法
一、什么是弗洛伊德算法？
弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。
该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
弗洛伊德算法(Floyd)：计算图中各个顶点之间的最短路径
迪杰斯特拉算法：用于计算图中某一个顶点到其他顶点的最短路径。
迪杰斯特拉算法：通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径
弗洛伊德算法中：每一个顶点都是出发访问点
我们从而求出：从每一个顶点到其他顶点的最短路径。
弗洛伊德(Floyd)算法过程
假如我们设定（L = Lenght ）
顶点vi到顶点vk的最短路径已知为Lik顶点vk到vj的最短路径已知为Lkj顶点vi到vj的路径为Lij
则vi到vj的最短路径为：min((Lik+Lkj),Lij)，
vk的取值为图中所有顶点，则可获得vi到vj的最短路径
至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得
二、通过示例来认识算法
弗洛伊德算法图解思路
根据示意图，画出他们的邻接矩阵，称为距离表
同时，当我们的代码还没开始求最短路径时，初始一个中间关系表
中间关系表有什么作用呢？让我们来距离一个顶点说明情况
比如说当前顶点是：A、B、C、D、E、F、G
从A开始，以A(下标为：0)作为中间顶点，更新距离表和中间关系表
那么是怎么做的呢？
首先把A作为中间节点的所有情况，都列举出来
- C -> A -> G ，
即A作为中间顶点，C-G的距离为：9（7+2） - C -> A -> B ，
即A作为中间顶点，C-B的距离为：12（7+5） - G -> A -> B ，
即A作为中间顶点，G-B的距离为：7（2+5）
这个时候将CAG、CAB、GAB更新到距离表
我们使用A作为中间顶点，所以可以过度的比较距离，修改距离表里的无
那么我们是使用中间顶点作为过度，那么还需要更新中间关系表
这就导致，原先某个顶点与某个顶点之间并没有连接的关系，原先为无
这时有了中间关系表，可以通过这个表来过度进行关联连接起来
那么问题来了：我怎么知道把A作为中间节点的所有连接情况
我们需要一个数组存放中间顶点：A、B、C、D、E、F、G
我们需要一个数组存放出发顶点：A、B、C、D、E、F、G
我们需要一个数组存放终点顶点：A、B、C、D、E、F、G
假如我们是以A作为中间顶点，那么就先从中间顶点数组取出来（下标）
从出发顶点选取第一个顶点：A，遍历所有终点顶点
当出发顶点的第一个顶点：A，做完后再取第二个、第三个....
中间顶点保持不变，直至出发顶点遍历完后，再取第二个中间顶点...
弗洛伊德算法思路
1.使用邻接矩阵来表示图所之间连接关系与权重值
//使用邻接矩阵描述权重值表示0 代表无int[][] weight = new int[][]{
{0,5,7,0,0,0,0},
{5,0,0,9,0,0,3},
{7,0,0,0,8,0,0},
{0,9,0,0,0,4,0},
{0,0,8,0,0,5,4},
{0,0,0,4,5,0,6},
{2,3,0,0,4,6,0}
};
2.需要一个存放顶点的char数组
//char[] 数组存放顶点个数char[] data = new char[]{'A','B','C','D','E','F','G'};
3.创建对象存放节点数据、距离表矩阵、中间关系表矩阵
class Mgraph{char[] data;//存放结点数据
int[][] weight;//存放各个顶点至其他顶点的距离
int[][] middle;//保存到达目标顶点的中间关系表
public Mgraph(char[] data, int[][] weight, int[][] middle) {
this.data = data;
this.weight = weight;
this.middle = middle;
}
}
同时，当我们的代码还没开始求最短路径时，初始一个中间关系表
所以我们的初始化的时候，代码也要编写一下
class Mgraph{//省略其他关键代码...
/**
*
* @param data 顶点数组
* @param weight 邻接矩阵
* @param lenght 大小
*/
public Mgraph(char[] data, int[][] weight, int lenght) {
this.data = data;
this.weight = weight;
this.middle = new int[lenght][lenght];
for(int i = 0;i<lenght;i++){
Arrays.fill(middle[i],i);
}
}
}
我们添加打印距离表、中间表的代码
class Mgraph{//省略其他关键代码....
public void showMiddle(){
for (int[] link:middle){
System.out.println(Arrays.toString(link));
}
}
public void showGraph(){
for (int[] link:weight){
System.out.println(Arrays.toString(link));
}
}
}
接下来我们使用demo 完成图的创建与输出
public static void main(String[] args) {//char[] 数组存放顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};
//使用邻接矩阵描述权重值表示0 代表无
int[][] weight = new int[][]{
{0,5,7,0,0,0,0},
{5,0,0,9,0,0,3},
{7,0,0,0,8,0,0},
{0,9,0,0,0,4,0},
{0,0,8,0,0,5,4},
{0,0,0,4,5,0,6},
{2,3,0,0,4,6,0}
};
Mgraph graph = new Mgraph(data ,weight,data.length);
graph.showGraph();
System.out.println("=======================================================");
graph.showMiddle();
}
诶，我们发现中间关系表 显得不是那么好看，我们可以优化一下
class Mgraph{//省略其他关键代码....
public void showMiddle(){
for (int i =0;i<middle.length;i++){
for (int j = 0; j<middle[i].length;j++){
System.out.print(data[middle[i][j]] + "\t");
}
System.out.println();
}
}
}
三、弗洛伊德算法编写
之前提到：假如我们是以A作为中间顶点，那么就先从中间顶点数组取出来（下标）
从出发顶点选取第一个顶点：A，遍历所有终点顶点
当出发顶点的第一个顶点：A，做完后再取第二个、第三个....
中间顶点保持不变，直至出发顶点遍历完后，再取第二个中间顶点...
第一步：从中间顶点开始，取第元素下标出来
class Mgraph{//省略其他关键代码....
public void flody(){
int len = 0;
//对中间关系表进行遍历,A、B、C、D、E、F、G
for(int k = 0; k<weight.length; k++){
}
}
}
第二步：从出发顶点开始，取元素下标出来，做完后再取第二个、第三个....
class Mgraph{//省略其他关键代码....
public void flody(){
int len = 0;
//对中间关系表进行遍历
for(int k = 0;k<weight.length;k++){
//对出发顶点进行遍历：A、B、C、D、E、F、G
for (int i = 0; i<weight.length;i++){
}
}
}
}
第三步：出发顶点遍历遍历所有终点顶点，所以还需要终点遍历
class Mgraph{//省略其他关键代码....
public void flody(){
int len = 0;
//对中间关系表进行遍历
for(int k = 0;k<weight.length;k++){
//对出发顶点进行遍历：A、B、C、D、E、F、G
for (int i = 0; i<weight.length;i++){
//出发顶点对终点顶点进行遍历：A、B、C、D、E、F、G
for (int j = 0; j<weight.length;j++){
}
}
}
}
}
第四步：计算出发顶点->中间顶点->终点顶点的距离是多少
假如像我们之前那样，采用A作为中间顶点，C作为出发节点
- C -> A -> G ，
即A作为中间顶点，C-G的距离为：9（7+2） - C -> A -> B ，
即A作为中间顶点，C-B的距离为：12（7+5）
按照我们的顶点顺序，A、B、C、D、E、F、G
假设我们求得是我们C-A-G、C-A、B，那么我们对应的值就为：
出发顶点：C（下标为二） i = 2
中间顶点：A（下标为零） k = 0
结束顶点：G（下标为六）、B（下标为二）j = 6、 j =2
那么我们求C-A-G，就要求C-A的距离加上A-G的距离
class Mgraph{//省略其他关键代码....
public void flody(){
int len = 0;
//对中间关系表进行遍历
for(int k = 0;k<weight.length;k++){
//对出发顶点进行遍历：A、B、C、D、E、F、G
for (int i = 0; i<weight.length;i++){
//出发顶点对终点顶点进行遍历：A、B、C、D、E、F、G
for (int j = 0; j<weight.length;j++){
//如果求 C-A-G，就要求 C-A 的距离加上 A-G的距离
//出发顶点：C（下标为二） i = 2
//中间顶点：A（下标为零） k = 0
//结束顶点：G（下标为六） G = 6
//C-A的距离 = weight[i][k]
//A-G的距离 = weight[k][j]
len = weight[i][k] + weight[k][j];
}
}
}
}
}
第五步：按照我们之前的思路，需要进行比较，若C-A-G的距离比C-G小
那么则将他们重置代替
1.这时我们需要获取C-G/G-C 的矩阵信息:weighti = 2
2.这时我们需要更新C-G/G-C 的中间表信息：middlek = 0
class Mgraph{//省略其他关键代码....
public void flody(){
int len = 0;
//对中间关系表进行遍历
for(int k = 0;k<weight.length;k++){
//对出发顶点进行遍历：A、B、C、D、E、F、G
for (int i = 0; i<weight.length;i++){
//出发顶点对终点顶点进行遍历：A、B、C、D、E、F、G
for (int j = 0; j<weight.length;j++){
//如果求C-A-G，就要求C-A的距离加上A-G的距离
//出发顶点：C（下标为二） i = 2
//中间顶点：A（下标为零） k = 0
//结束顶点：G（下标为六） G = 6
//C-A的距离 = weight[i][k]
//A-G的距离 = weight[k][j]
len = weight[i][k] + weight[k][j];
//出发顶点：C（下标为二） i = 2
//结束顶点：G（下标为六） G = 6
//获取C-G/G-B 的矩阵信息 [2][6]
if(len <weight[i][j]){
weight[i][j] = len;
middle[i][j] = middle[k][j];
}
}
}
}
}
}
接下来我们添加一个方法，看看调用算法后，各个顶点至其他顶点的距离是多少
class Mgraph{//省略其他关键代码....
public void showResult(){
for (int i =0;i<weight.length;i++){
for (int j = 0; j<weight.length;j++){
System.out.println("("+data[i]+")"+"到"+"("+data[j]+")"+",的距离是"+weight[i][j]);
}
System.out.println();
System.out.println("================================================================");
}
}
}
接下来我们使用demo 方法调用输出看看
public static void main(String[] args) {//char[] 数组存放顶点个数
char[] data = new char[]{'A','B','C','D','E','F','G'};
int maxValue = 6535;
//使用邻接矩阵描述权重值表示0 代表无
int[][] weight = new int[][]{
{0,5,7,maxValue,maxValue,maxValue,2},
{5,0,maxValue,9,maxValue,maxValue,3},
{7,maxValue,0,maxValue,8,maxValue,maxValue},
{maxValue,9,maxValue,0,maxValue,4,maxValue},
{maxValue,maxValue,8,maxValue,0,5,4},
{maxValue,maxValue,maxValue,4,5,0,6},
{2,3,maxValue,maxValue,4,6,0}
};
Mgraph graph = new Mgraph(data ,weight,data.length);
graph.flody();
graph.showResult();
}
运行结果如下：
(A)到(A),的距离是0
(A)到(B),的距离是5
(A)到(C),的距离是7
(A)到(D),的距离是12
(A)到(E),的距离是6
(A)到(F),的距离是8
(A)到(G),的距离是2
================================================================
(B)到(A),的距离是5
(B)到(B),的距离是0
(B)到(C),的距离是12
(B)到(D),的距离是9
(B)到(E),的距离是7
(B)到(F),的距离是9
(B)到(G),的距离是3
================================================================
(C)到(A),的距离是7
(C)到(B),的距离是12
(C)到(C),的距离是0
(C)到(D),的距离是17
(C)到(E),的距离是8
(C)到(F),的距离是13
(C)到(G),的距离是9
================================================================
(D)到(A),的距离是12
(D)到(B),的距离是9
(D)到(C),的距离是17
(D)到(D),的距离是0
(D)到(E),的距离是9
(D)到(F),的距离是4
(D)到(G),的距离是10
================================================================
(E)到(A),的距离是6
(E)到(B),的距离是7
(E)到(C),的距离是8
(E)到(D),的距离是9
(E)到(E),的距离是0
(E)到(F),的距离是5
(E)到(G),的距离是4
================================================================
(F)到(A),的距离是8
(F)到(B),的距离是9
(F)到(C),的距离是13
(F)到(D),的距离是4
(F)到(E),的距离是5
(F)到(F),的距离是0
(F)到(G),的距离是6
================================================================
(G)到(A),的距离是2
(G)到(B),的距离是3
(G)到(C),的距离是9
(G)到(D),的距离是10
(G)到(E),的距离是4
(G)到(F),的距离是6
(G)到(G),的距离是0
================================================================
以上是 【Java】我所知道的十大常用算法之费洛伊德算法（最短路径） 的全部内容， 来源链接： utcz.com/a/96785.html
