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

### 一、什么是弗洛伊德算法？

#### 弗洛伊德(Floyd)算法过程

• `顶点vi到顶点vk的最短路径已知为Lik`
• `顶点vk到vj的最短路径已知为Lkj`
• `顶点vi到vj的路径为Lij`

vk的取值为图中所有顶点，则可获得vi到vj的最短路径

### 二、通过示例来认识算法

#### 弗洛伊德算法图解思路

• 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）`

#### 弗洛伊德算法思路

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

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

### 三、弗洛伊德算法编写

``````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++){
}
}
}
}
}``````

• C -> A -> G ，`即A作为中间顶点，C-G的距离为：9（7+2）`
• C -> A -> B ，`即A作为中间顶点，C-B的距离为：12（7+5）`

``````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];
}
}
}
}
}``````

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

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