Java版-图论-最短路-Floyd算法

实现描述

网络延迟时间示例

根据上面提示，可以计算出，最大有100个点，最大耗时为100*wi,即最大的耗时为10000，任何耗时计算出来超过这个值可以理解为不可达了；从而得出实现代码里面的：

int maxTime = 10005; //这里是题目给出的最大距离

1. 定义数组w[i][j]=weight; 其中，表示从i->j需要耗时weight;
2. 求解从k出发，到其他各个点的最短时间，需要算出从k出发到其余各个点的时间取最大值；
3. 利用中间点middle,从i->j的距离，如果经过中间点middle，则w[i][j]=w[i][middle]+w[middle][j];
4. 利用状态转移，可以dp出w的矩阵值，然后计算从k出发到各个点的时间，进而求出时间的最大值；

实现代码

 public static void main(String[] args) {
//        int[][] times = {
//                {2, 1, 1},
//                {2, 3, 1},
//                {3, 4, 1}};
//        int n = 4; //4个节点
//        int k = 2; //从2int[][] times = {{1, 2, 1}};int n = 2; int k = 2; System.out.println(new Floyd().networkDelayTime(times, n, k));}int[][] matrix;public int networkDelayTime(int[][] times, int n, int k) {int result = -1;matrix = new int[n + 1][n + 1];int maxTime = 10005; //这里是题目给出的最大距离for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) {matrix[i][j] = 0;} else {matrix[i][j] = maxTime;}}}//初始化矩阵实际值for (int[] time : times) {int from = time[0], to = time[1];matrix[from][to] = time[2];}floydAlgorithm(n, matrix);for (int i = 1; i <= n; i++) {result = Math.max(result, matrix[k][i]);}return result >= maxTime ? -1 : result;}void floydAlgorithm(int n, int[][] matrix) {for (int middle = 1; middle <= n; middle++) {  //中转点for (int i = 1; i <= n; i++) { //起点for (int j = 1; j <= n; j++) { //终点matrix[i][j] = Math.min(matrix[i][j], matrix[i][middle] + matrix[middle][j]);}}}}