最短路径-Floyd弗洛伊德算法

圆号本昊

发布于 2021-09-24 14:34:05

32800

代码可运行

文章被收录于专栏：github@hornhuanggithub@hornhuang

运行总次数：0

代码可运行

文末给出实现的具体代码

弗洛伊德算法类似于迪杰特斯拉算法

他们的区别在于：

1.弗洛伊德算法时间复杂度O(N³) 而迪杰特斯拉算法为O(N²)

那么为什么要学会弗洛伊德算法呢？

1.弗洛伊德算法更通俗易懂

2.弗洛伊德算法可以求和所有点之间的最短路径

本文采用java语言实现该算法

首先请看该算法的实现：

要实现佛洛依德算法你需要定义两个二维数组

一个用于存储路径长度 //这里我取名diatance

另一个用于存储父母及前一交点位置 //取名parent

具体实现原理参照https://www.bilibili.com/video/av2975983/?p=66

这里我封为两部分

一部分是initialize() 用于初始化数组

另一部份就是算法实体findShort()方法

算法其实及其简单：

for (int temp = 0; temp < distance.length; temp++) {
	for (int i = 0; i < distance.length; i++) {
		for (int j = 0; j < distance.length; j++) {
			if (distance[i][temp]!= Integer.MAX_VALUE && distance[temp][j]!= Integer.MAX_VALUE) {
				if (distance[i][j] > ( distance[i][temp] + distance[temp][j] )) {
					distance[i][j] = ( distance[i][temp] + distance[temp][j] );
					parent[i][j] = parent[i][temp];
				}	
			}
			
		}
	}
}

真正替换操作只有两句：

distance[i][j] = ( distance[i][temp] + distance[temp][j] );
parent[i][j] = parent[i][temp];

替换了原路线和原油父母节点

这里给出测试范例：

1.输入范例：

2.输出范例

最后给出完整的实现如下：

public class Floyd {
	//矩阵大小  图中点数
	int num ;
	//距离矩阵
	int distance[][] ;
	//父母矩阵
	int parent[][] ;
	/*
	 * 构造方法
	 */
	public Floyd() {
		super();
		distance = new int[0][0];
		parent = new int[0][0];
	}
	
	public Floyd(int[][] distance, int[][] parent) {
		super();
		this.distance = distance;
		this.parent = parent;
	}
	
	
	public Floyd(int num) {
		super();
		this.num = num;
		this.distance = new int[num][num];
		this.parent = new int[num][num];
	}

	/*
	 * 初始化所有矩阵方法
	 */
	private void initialize() {
		for(int i = 0 ; i < distance.length ; i++ ){
			for(int j = 0 ; j < distance.length ; j++ ){
				parent[i][j] = j ;
			}
		}
	}
	
	/*
	 * 三次循环找到所有最短路径
	 */
	public void findShort() {
		//更新矩阵
		initialize();
		//三个循环 设定所有
		for (int temp = 0; temp < distance.length; temp++) {
			for (int i = 0; i < distance.length; i++) {
				for (int j = 0; j < distance.length; j++) {
					if (distance[i][temp]!= Integer.MAX_VALUE && distance[temp][j]!= Integer.MAX_VALUE) {
						if (distance[i][j] > ( distance[i][temp] + distance[temp][j] )) {
							distance[i][j] = ( distance[i][temp] + distance[temp][j] );
							parent[i][j] = parent[i][temp];
						}	
					}
					
				}
			}
		}
	}
	
	/*
	 * get set 方法
	 */
	public int[][] getDiatance() {
		return distance;
	}
	public void setDiatance(int[][] diatance) {
		this.distance = diatance;
	}
	public int[][] getParent() {
		return parent;
	}
	public void setParent(int[][] parent) {
		this.parent = parent;
	}
	
}

测试类：

public class Main {
	public static void main(String[] args) {
		System.out.println(Integer.MAX_VALUE+5);
		int distance[][] = new int[][]{
			{0,1,5,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
			{1,0,3,7,5,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
			{5,3,0,Integer.MAX_VALUE,1,7,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
			{Integer.MAX_VALUE,7,Integer.MAX_VALUE,0,2,Integer.MAX_VALUE,3,Integer.MAX_VALUE,Integer.MAX_VALUE},
			{Integer.MAX_VALUE,5,1,2,0,3,6,9,Integer.MAX_VALUE},
			{Integer.MAX_VALUE,Integer.MAX_VALUE,7,Integer.MAX_VALUE,3,0,Integer.MAX_VALUE,5,Integer.MAX_VALUE},
			{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,6,Integer.MAX_VALUE,0,2,7},
			{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,9,5,2,0,4},
			{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,7,4,0},
		};
		for(int i = 0 ; i < 9 ; i++ ){
			for(int j = 0 ; j < 9 ; j++){
				if(distance[i][j] == 1000){
					distance[i][j] = 0;
				}
			}
		}
		int parent[][] = new int[9][9];
		for(int i = 0 ; i < 9 ; i++ ){
			for(int j = 0 ; j < 9 ; j++){
				parent[i][j] = j ;
			}
		}
		Floyd floyd = new Floyd(distance, parent);
		floyd.findShort();
		distance = floyd.getDiatance();
		parent = floyd.getParent();
		System.out.println("\n\n\n\n\nDISTANCE");
		//distance
		for(int i = 0 ; i < 9 ; i++ ){
			for(int j = 0 ; j < 9 ; j++){
				System.out.print(distance[i][j] + " "); ;
			}
			System.out.println();
		}
		//parent
		System.out.println("\n\n\n\n\nPARENT");
		for(int i = 0 ; i < 9 ; i++ ){
			for(int j = 0 ; j < 9 ; j++){
				System.out.print(parent[i][j] + " "); ;
			}
			System.out.println();
		}
	} 
}

输出如下：