H5W3
当前位置:H5W3 > java > 正文

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

前言需求


今天我们学习的是弗洛伊德算法,我们还是从一个场景里引入看看

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

战争时期,胜利乡有7个村庄(A, B, C, D, E, F, G)

有一名邮差需要你的帮忙:从G点出发,分别把邮件分别送到 A, B, C , D, E, F 六个村庄

问:如何计算出各村庄到其它各个村庄的最短距离?

各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里

如我们问的是:如何计算出G村庄到 其它各个村庄的最短距离?

那么采用我们之前的方式:迪杰斯特拉算法(最短路径)

但是我们今天问的是:如何计算出各村庄到其它各个村庄的最短距离?

所以今天我们我们使用新的算法来解决这个问题:弗洛伊德算法

一、什么是弗洛伊德算法?

弗洛伊德(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,是以同样的方式获得

二、通过示例来认识算法

弗洛伊德算法图解思路

根据示意图,画出他们的邻接矩阵,称为距离表

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

同时,当我们的代码还没开始求最短路径时,初始一个中间关系表

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

中间关系表有什么作用呢?让我们来距离一个顶点说明情况

比如说当前顶点是: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更新到距离表

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)
【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)
【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

我们使用A作为中间顶点,所以可以过度的比较距离,修改距离表里的无

那么我们是使用中间顶点作为过度,那么还需要更新中间关系表

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

这就导致,原先某个顶点与某个顶点之间并没有连接的关系,原先为无

这时有了中间关系表,可以通过这个表来过度进行关联连接起来

那么问题来了:我怎么知道把A作为中间节点的所有连接情况

我们需要一个数组存放中间顶点:A、B、C、D、E、F、G

我们需要一个数组存放出发顶点:A、B、C、D、E、F、G

我们需要一个数组存放终点顶点:A、B、C、D、E、F、G

假如我们是以A作为中间顶点,那么就先从中间顶点数组取出来(下标)

从出发顶点选取第一个顶点:A,遍历所有终点顶点

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

当出发顶点的第一个顶点:A,做完后再取第二个、第三个….

中间顶点保持不变,直至出发顶点遍历完后,再取第二个中间顶点…

弗洛伊德算法思路

1.使用邻接矩阵来表示图所之间连接关系与权重值

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)
【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

//使用邻接矩阵描述权重值表示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;
}
}

同时,当我们的代码还没开始求最短路径时,初始一个中间关系表

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

所以我们的初始化的时候,代码也要编写一下

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();
}

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

诶,我们发现中间关系表 显得不是那么好看,我们可以优化一下

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();
}
}
}

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

三、弗洛伊德算法编写

之前提到:假如我们是以A作为中间顶点,那么就先从中间顶点数组取出来(下标)

从出发顶点选取第一个顶点:A,遍历所有终点顶点

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

当出发顶点的第一个顶点: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

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

假设我们求得是我们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小

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

那么则将他们重置代替

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
================================================================

本文地址:H5W3 » 【Java】我所知道的十大常用算法之费洛伊德算法(最短路径)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址