弗洛伊德算法怎么理解_弗洛伊德算法思想

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

这个方法中，其中每一个顶点到另一个顶点最多就是两步。
所以就是找到两个顶点的最近距离

package a;
import java.lang.reflect.Array;
import java.util.Arrays;
public class FloydDemo { 

public static void main(String[] args) { 

char[] diots = { 
'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int[][] edges = new int[diots.length][diots.length];
final int N = 65535;
edges[0]=new int[]{ 
0,5,7,N,N,N,2};//注意这个自身到自身的距离是0 ，并不是N 和地杰斯特拉的区别
edges[1]=new int[]{ 
5,0,N,9,N,N,3};
edges[2]=new int[]{ 
7,N,0,N,8,N,N};
edges[3]=new int[]{ 
N,9,N,0,N,4,N};
edges[4]=new int[]{ 
N,N,8,N,0,5,4};
edges[5]=new int[]{ 
N,N,N,4,5,0,6};
edges[6]=new int[]{ 
2,3,N,N,4,6,0};
FGraph fGraph = new FGraph(diots, edges, diots.length);
fGraph.floyd();
fGraph.show();
}
}
class FGraph{ 

char [] data;
int [] [] dis;
int [][] pre;
public FGraph(char[] data, int[][] dis, int len) { 

this.data = data;
this.dis = dis;
pre = new int[len][len];
for (int i = 0; i < data.length; i++) { 

Arrays.fill(pre[i],i);//每个顶点的前驱节点默认值是自身的下标。和地杰斯特拉不一样，地杰斯特拉默认不初始化。
}
}
public void show(){ 

for (int i = 0; i < data.length; i++) { 

for (int j = 0; j < data.length; j++) { 

System.out.print(data[pre[i][j]]+"\t");
}
System.out.println();
for (int j = 0; j < data.length; j++) { 

System.out.print("("+data[i]+"-->"+data[j]+":"+dis[i][j]+"|\t");
}
System.out.println();
}
}
public void floyd(){ 

int len =0;//变量保存距离
for (int i = 0; i < data.length; i++) { 
//中间
for (int j = 0; j < data.length; j++) { 
//起点
for (int k = 0; k < data.length; k++) { 
//终点
len = dis[j][i]+dis[i][k];
if (len < dis[j][k]) { 

dis[j][k] = len;
pre[j][k] = pre[i][k];//这个是更新前一个顶点。在初始化的时候pre 的每一行都是 自身。所以，这个第一次是自身。然后变成了中间的这个点。
}
}
}
}
}
}

Jetbrains全家桶1年46，售后保障稳定