算法-数据结构(图)-弗洛伊德算法复现（Floyd）

弗洛伊德算法（Floyd-Warshall算法）是一种用于求解所有节点对最短路径的动态规划算法，适用于有向图或无向图，且能处理带有负权边的图（但不能有负权环）。该算法的时间复杂度为 O(V3)O(V3)，其中 VV 是图的节点数。

---

核心思想

弗洛伊德算法通过逐步优化路径来求解最短路径。其核心思想是：

对于任意两个节点 ii 和 jj，检查是否存在一个中间节点 kk，使得从 ii 到 jj 的路径可以通过 kk 变得更短。

通过动态规划逐步更新最短路径。

---

算法步骤

初始化：

创建一个距离矩阵 DD，其中 D[i][j]D[i][j] 表示节点 ii 到节点 jj 的最短路径长度。

如果 ii 和 jj 之间有直接边，则 D[i][j]D[i][j] 为边的权重；否则为无穷大（∞∞）。

对角线上的值 D[i][i]D[i][i] 初始化为 0（节点到自身的距离为 0）。

动态规划更新：

对于每一个中间节点 kk（从 1 到 VV），更新所有节点对 ii 和 jj 的最短路径：

D[i][j]=min⁡(D[i][j],D[i][k]+D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j])

即，检查是否通过节点 kk 可以使 ii 到 jj 的路径更短。

结束：

当所有中间节点 kk 都被遍历后，矩阵 DD 中的值即为所有节点对的最短路径。

手动推导：

算法如下：

public class Foloyd { //弗洛伊德最短路径算法复现 public static void Floyd(int [] [] dist, int [][] path) { int L=dist.length; for(int k=0;k<L;k++) { for(int i=0;i<L;i++) { for(int j=0;j<L;j++) { if(dist[i][k]!=Integer.MAX_VALUE&&dist[k][j]!=Integer.MAX_VALUE) { //判断是否通过中转路径能更短 if(dist[i][k]+dist[k][j]<dist[i][j]) { //更新距离 dist[i][j]=dist[i][k]+dist[k][j]; //中转点 path[i][j]=k; } } } } } System.out.println("最短路径值为："); for(int i=0;i<L;i++) { for(int j=0;j<L;j++) { System.out.print(dist[i][j]); System.out.print(" "); } System.out.println(); } System.out.println("最短路径为："); for(int i=0;i<L;i++) { for(int j=0;j<L;j++) { System.out.print(path[i][j]); System.out.print(" "); } System.out.println(); } } public static void main(String[] args) { int[][] vG= {{0,6,13}, {10,0,4}, {5,Integer.MAX_VALUE,0}}; int[][] path={{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}}; Floyd(vG,path); } }

结果如下：

最短路径值为： 0 6 10 9 0 4 5 11 0 最短路径为： -1 -1 1 2 -1 -1 -1 0 -1