算法——弗洛伊德算法（求最短路径 Java代码实现）

分手后的思念是犯贱 2023-02-14 06:54 516阅读 0赞

前文：迪杰斯特拉算法 [单击前往][Link 1]

#### 弗洛伊德(Floyd)算法介绍 ####

1.  和迪杰斯特拉算法一 样， 弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。
2.  弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
3.  迪杰斯特拉算法用于计算图中某-一个顶点到其他项点的最短路径。
4.  弗洛伊德算法VS迪杰斯特拉算法:迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他项点的最短路径:弗洛伊德算法中每-个顶点都是出发访问点，所以需要将每-一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

### 弗洛伊德(Floyd)算法思想 ###

1.  设置项点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min((Lik，Lij)，Lij), vk的取值为图中所有顶点，则可获得vi到vj的最短路径
2.  至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得

#### 图解： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
面对问题：求出每一个点到其他点的距离；  
![在这里插入图片描述][20200530162545349.png]  
代码实现：

package FloydAlgorithm;
    
    import java.util.Arrays;
    
    public class Floyd { 
    	public static void main(String[] args) { 
    		char[] vertex = new char[] {  'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    		int[][] arr = new int[vertex.length][vertex.length];
    		final int N = 100;
    		arr[0] = new int[] {  0, 5, 7, N, N, N, 2 };
    		arr[1] = new int[] {  5, 0, N, 9, N, N, 3 };
    		arr[2] = new int[] {  7, N, 0, N, 8, N, N };
    		arr[3] = new int[] {  N, 9, N, 0, N, 4, N };
    		arr[4] = new int[] {  N, N, 8, N, 0, 5, 4 };
    		arr[5] = new int[] {  N, N, N, 4, 5, 0, 6 };
    		arr[6] = new int[] {  2, 3, N, N, 4, 6, 0 };
    		Graph gp = new Graph(vertex, arr, vertex.length);
    		gp.floyd();
    		gp.show();
    	}
    }
    
    //创建图
    class Graph { 
    	private char[] vertex;
    	private int[][] dis; // 从顶点出发到其他节点的距离
    	private int[][] pre; // 目标节点的前驱节点
    
    	// 顶点数组 邻接矩阵 长度大小
    	public Graph(char[] vertex, int[][] dis, int len) { 
    		this.vertex = vertex;
    		this.dis = dis;
    		this.pre = new int[len][len];
    		// 对pre数组进行初始化
    		for (int i = 0; i < len; i++) { 
    			Arrays.fill(pre[i], i);
    		}
    	}
    
    	public void show() { 
    		char[] vertex = new char[] {  'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    		for (int i = 0; i < dis.length; i++) { 
    			for (int j = 0; j < dis.length; j++) { 
    				System.out.print(vertex[pre[i][j]] + " ");
    			}
    			System.out.println();
    			for (int j = 0; j < dis.length; j++) { 
    				System.out.print("( " + vertex[i] + " -> " + vertex[j] + " 的最短路径 " + dis[i][j] + " ) ");
    			}
    			System.out.println();
    		}
    	}
    
    	// 弗洛伊德算法
    	public void floyd() { 
    		int len = 0;
    		// 从中间节点进行遍历
    		for (int k = 0; k < dis.length; k++) { 
    			// 对出发节点进行遍历
    			for (int i = 0; i < dis.length; i++) { 
    				// 遍历终点节点
    				for (int j = 0; j < dis.length; j++) { 
    					len = dis[i][k] + dis[k][j];
    					if (len < dis[i][j]) { 
    						dis[i][j] = len;
    						pre[i][j] = pre[k][j];
    					}
    				}
    			}
    		}
    	}
    }

对运行结果进行判断：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]

[Link 1]: https://blog.csdn.net/qq_44973159/article/details/106459539
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020060116391448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[20200530162545349.png]: https://img-blog.csdnimg.cn/20200530162545349.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200601182547806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70