avatar

java弗洛伊德算法(最短路径问题)

java弗洛伊德算法(最短路径问题)

package com.csw.algorithm.floyd;

import sun.security.util.Length;

import java.util.Arrays;

/**
* @Auther: 行路
* @Date: Created on 2020/5/8 16:06 星期五
* @Description: com.csw.algorithm.floyd
* @version: 1.0 弗洛伊德算法
*/
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(){
//为了显示便于阅读,优化输出
for(int k=0;k<dis.length;k++){
//先将pre数组输出一行数据
for(int i=0;i<dis.length;i++){
System.out.print(vertex[pre[k][i]]+" ");
}
System.out.println("");
//输出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++){
len=dis[i][k]+dis[k][j]; //从i顶点出发,经过k中间顶点,到达J顶点距离
if(len<dis[i][j]){
//如果len小于dis[i][j]
dis[i][j]=len; //更新距离
pre[i][j]=pre[k][j]; //更新前驱节点
}
}
}
}
}

}
文章作者: Todcsw
文章链接: https://todcsw.github.io/2020/05/08/dataStructure-java%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95-%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E9%97%AE%E9%A2%98/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 行路のblog
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论