743. Network Delay Time

Question

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

  1. N will be in the range [1, 100].
  2. K will be in the range [1, N].
  3. The length of times will be in the range [1, 6000].
  4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Solution:

  • Method 1: Floyd O(n ^ 3) 
    class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[][] cost = new int[N + 1][N + 1];
        for(int[] c : cost) Arrays.fill(c, Integer.MAX_VALUE >> 1);
        for(int i = 1; i <= N; i++) cost[i][i] = 0;
        for(int[] time : times){
            cost[time[0]][time[1]] = time[2];
        }
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= N; i++){
            if(cost[K][i] > 6000) return -1;
            res = Math.max(res, cost[K][i]);
        }
        return res;
    }
}
  • Method 2: Dijkstra 
    class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[][] cost = new int[N + 1][N + 1];
        for(int[] c : cost) Arrays.fill(c, Integer.MAX_VALUE >> 1);
        for(int i = 1; i <= N; i++) cost[i][i] = 0;
        for(int[] time : times){
            cost[time[0]][time[1]] = time[2];
        }
        int[] result = Arrays.copyOf(cost[K], N + 1);
        Set<Integer> set = new HashSet<>();
        set.add(K);
        while(set.size() < N){
            int index = -1, min = Integer.MAX_VALUE;
            for(int i = 1; i <= N; i++){
                if(!set.contains(i) && min > result[i]){
                    index = i;
                    min = result[i];
                }
            }
            for(int i = 0; i <= N; i++){
                if(index != -1 && !set.contains(i)){
                    result[i] = Math.min(result[i], min + cost[index][i]);
                }
            }
            if(index == -1) return -1;
            else set.add(index);
        }
        int res = 0;
        for(int i = 1; i <= N; i++){
            if(result[i] > 6000) return -1;
            res = Math.max(result[i], res);
        }
        return res;
    }
}