743. Network Delay Time

In fact, the network delay time is the max shortest distance begin from source node to a certain node. Apparently, we can use Dijkstra algorithm to solve this problem:

1. distance[i] denotes the distance from K to i, used[i] denotes whether node i has been processed;
2. Each time we choose a unprocessed node j where distance[j] is the minimum among those unprocessed nodes;
3. Traverse distance to update the minimum distance where j is the intermediate node;
4. network delay = {distance[i] | For any 1 <= j <= N, distance[i] >= distance[j]}

Note that if we cannot find a valid unprocessed node in step 2, just return -1.

public int networkDelayTime(int[][] times, int N, int K) {
    // 1. Initiliaze used and distance
    boolean used[] = new boolean[N + 1];
    used[K] = true;
    int distance[] = new int[N + 1];
    Arrays.fill(distance, Integer.MAX_VALUE);
    distance[K] = 0;

    for(int i = 0; i < times.length; i++) {
        if( times[i][0] == K ) {
            distance[times[i][1]] = times[i][2];
        }
    }
    for(int i = 1; i < N; i++) {
	// 2. Find a valid unprocessed node
        int min = Integer.MAX_VALUE;
        int choosen = -1;
        for(int j = 1; j <= N; j++) {
            if( !used[j] && distance[j] < min ) {
                min = distance[j];
                choosen = j;
            }
        }
        if( choosen == -1 ) 
            return -1;
        used[choosen] = true;
		
	// 3. Update distance
        for(int j = 0; j < times.length; j++) {
            if( times[j][2] + distance[times[j][0]] < distance[times[j][1]] )
                distance[times[j][1]] = times[j][2] + distance[times[j][0]];
        }
    }

    // 4. Calculate network delay
    int result = 0;
    for(int i = 1; i <= N; i++) {
        result = Math.max(result, distance[i]);
    }
    return result;
}