7.6.2弗洛伊德(Floyd)算法
Floyd主要计算多源最短路径。
算法的具体思想为：
邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.- 从
第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。- 而上述试探具体方法为遍历图中每一个点(i,j双重循环) ，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。
- 重复上述直到最后插点试探完成。
默认的最短长度初始为邻接矩阵初始状态
- 加入第一个节点
1,大家可以发现，由于1的加入，使得本来不连通的2，3点对和2，4点对变得联通，并且加入1后距离为当前最小。(可以很直观加入5之后2，4，更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条。(2,3)和(2,4).我们在dp中不管这个结果是通过前面那些步骤来的，但是在这个状态，这两点的最短距离就算它！
核心代码
public class floyd { static int max = 66666;// 别Intege.max 两个相加越界为负 public static void main(String[] args) { int dist[][] = { { 0, 2, 3, 6, max, max }, { 2, 0, max, max,4, 6 }, { 3, max, 0, 2, max, max }, { 6, max, 2, 0, 1, 3 }, { max, 4, max, 1, 0, max }, { max, 6, max, 3, max, 0 } };// 地图 // 6个 for (int k = 0; k < 6; k++)// 加入滴k个节点 { for (int i = 0; i < 6; i++)// 松弛I行 { for (int j = 0; j < 6; j++)// 松弛i列 { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } // 输出 for (int i = 0; i < 6; i++) { System.out.print("节点"+(i+1)+" 的最短路径"); for (int j = 0; j < 6; j++) { System.out.print(dist[i][j]+" "); } System.out.println(); } } }
