P743NetworkDelayTime.java

package graph;

import java.util.HashMap;

/**
 * Title: 743. 网络延迟时间
 * Desc:  有 N 个网络节点，标记为 1 到 N。
 *
 * 给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
 *
 * 现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
 *
 * Created by Myth-Lab on 10/25/2019
 */
public class P743NetworkDelayTime {
    // times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2         output:2
    public int networkDelayTime(int[][] times, int N, int K) {
        // 构建邻接矩阵
        int[][] graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = -1;
            }
        }
        for (int i = 0; i < times.length; i++) {
            graph[times[i][0]-1][times[i][1]-1] = times[i][2];  // 注意下标从0开始
        }
        return dijkstra(graph, N, K-1);
    }
    // 寻找连接的最小的点，不存在，返回 -1；
    private int findMinVertex(int[] distance, boolean[] visited) {
        int minValue = Integer.MAX_VALUE, minVertex = -1;
        for (int i = 0; i < distance.length; i++) {
            if (!visited[i] && distance[i] < minValue) {
                minValue = distance[i];
                minVertex = i;
            }
        }
        return minVertex;
    }
    public int dijkstra(int[][] graph, int N, int src) {
        int[] distance = new int[N];
        boolean[] visited = new boolean[N];
        HashMap<Integer, Integer> retMap = new HashMap<>();
        int ret = -1;
        for (int i = 0; i < N; i++) {
            if (graph[src][i] != -1) distance[i] = graph[src][i];
            else distance[i] = Integer.MAX_VALUE;
        }
        visited[src] = true;
        for (int i = 0; i < N-1; i++) {
            int minVertex = findMinVertex(distance, visited);
            if (minVertex == -1) return -1;  // 有无法抵达的点
            visited[minVertex] = true;
            retMap.put(minVertex, distance[minVertex]);
            ret = Math.max(ret, distance[minVertex]);  // 更新最大
            // 更新 distance
            for (int j = 0; j < N; j++) {
                if (graph[minVertex][j] != -1 && !visited[j] && distance[minVertex]+graph[minVertex][j] < distance[j]) {
                    distance[j] = distance[minVertex] + graph[minVertex][j];
                }
            }
        }
        // System.out.println(retMap.toString());
        return ret;
    }

    public static void main(String[] args) {
        int[][] times1 = {{1,2,1}};
        int[][] times2 = {{3,5,78},{2,1,1},{1,3,0},{4,3,59},{5,3,85},{5,2,22},{2,4,23},{1,4,43},{4,5,75},{5,1,15},{1,5,91},{4,1,16},{3,2,98},{3,4,22},{5,4,31},{1,2,0},
                {2,5,4},{4,2,51},{3,1,36},{2,3,59}};
        int[][] times3 = {{15,8,1},{7,10,41},{7,9,34},{9,4,31},{12,13,50},{14,3,52},{4,11,99},{4,7,86},{10,13,57},{9,6,10},{1,7,51},{7,15,38},{1,9,11},{12,7,94},{9,13,34},{11,7,79},{7,6,28},{5,3,34},{2,6,97},{14,1,97},{6,10,90},{12,10,37},{13,3,73},{11,14,7},{15,1,39},{6,5,90},{13,6,43},{6,9,32},{4,6,45},{11,10,2},{2,13,4},{14,15,29},{1,14,88},{14,6,19},{6,2,29},{3,14,72},{1,15,4},{11,5,2},{6,7,56},{8,7,88},{13,14,70},{14,12,58},{14,2,86},{11,3,57},{5,2,56},{3,10,26},{2,11,21},{14,5,54},{5,12,40},{14,4,81},{15,2,99},{5,7,57},{13,12,5},{4,9,60},{12,15,48},{6,14,1},{9,7,44},{13,7,69},{5,13,42},{4,1,7},{11,9,76},{8,1,76},{5,14,29},{2,3,69},{7,3,23},{12,14,28},{11,4,85},{10,1,10},{15,12,36},{1,11,69},{15,10,96},{11,13,69},{7,12,49},{1,2,95},{6,4,46},{8,12,94},{12,4,93},{13,5,31},{12,2,60},{6,1,87},{4,14,20},{5,11,89},{4,15,88},{4,10,21},{1,6,5},{10,8,26},{8,2,51},{3,15,23},{7,2,12},{11,1,47},{2,1,75},{3,8,63},{8,10,19},{6,8,18},{4,2,55},{14,11,80},{10,3,73},{3,5,22},{12,3,61},{1,13,33},{9,3,98},{9,12,69},{15,9,6},{7,13,76},{11,12,22},{11,15,51},{13,15,46},{5,10,58},{1,10,26},{13,4,85},{7,14,58},{5,8,46},{11,6,32},{10,9,41},{9,14,35},{14,13,60},{3,9,97},{2,5,39},{7,11,19},{1,12,27},{7,5,13},{8,4,34},{9,15,25},{5,1,93},{15,13,97},{14,9,35},{8,6,67},{9,5,39},{13,11,35},{7,4,21},{12,9,64},{14,8,8},{10,12,94},{8,9,76},{8,5,71},{2,9,64},{10,14,59},{1,4,74},{7,1,69},{15,5,55},{6,15,80},{13,8,84},{8,13,63},{8,3,91},{10,4,87},{1,5,39},{8,11,0},{1,3,79},{4,5,82},{4,12,87},{3,11,29},{7,8,92},{10,7,77},{6,12,42},{13,2,40},{9,10,13},{4,13,65},{2,4,34},{3,13,44},{2,14,69},{3,4,42},{5,15,98},{14,7,6},{15,3,94},{10,2,37},{15,11,7},{9,2,15},{13,9,66},{4,8,83},{8,15,23},{13,1,50},{6,13,57},{2,10,37},{10,6,38},{2,7,45},{9,8,8},{3,12,28},{3,2,83},{2,12,75},{1,8,91},{4,3,70},{12,6,48},{3,1,13},{5,6,42},{6,11,96},{3,6,22},{15,6,34},{11,8,43},{15,7,40},{9,11,57},{11,2,11},{2,8,22},{9,1,73},{2,15,40},{12,11,10},{15,4,78},{12,8,75},{10,15,37},{13,10,44},{8,14,33},{3,7,82},{5,4,46},{12,5,79},{15,14,43},{10,5,65},{5,9,34},{12,1,54},{6,3,16},{14,10,83},{10,11,67}};
        P743NetworkDelayTime p743 = new P743NetworkDelayTime();
        System.out.println(p743.networkDelayTime(times1, 2, 2));  // -1
        System.out.println(p743.networkDelayTime(times2, 5, 5));  // 31
        System.out.println(p743.networkDelayTime(times3, 15, 8));  // 34
    }

}