743. Network Delay Time - Medium

前往題目

思路

可用任意找最小路徑算法

1. 建立鄰接表
2. 利用BFS疊代起始點出發的每一層node並更新最短路徑
3. 最後因為要知道所有node都接收到signal需要多少時間，所以取最大值

Code

以下是來自discussion的答案，比較好理解，沒有用到priority queue

class Solution {
    /*
Step 1: Create a Map of start and end nodes with weight
        1 -> {2,1},{3,2}
        2 -> {4,4},{5,5}
        3 -> {5,3}
        4 ->
        5 ->

Step 2: create a result array where we will keep track the minimum distance to rech end of the node from start node

Step 3: Create a Queue and add starting position with it's weight and add it's reachable distance with increament of own't weight plus a weight require to reach at the end node from start node.
        We keep adding and removing pairs from queue and updating result array as well.

Step 4: find the maximum value from result array:

*/
    public int networkDelayTime(int[][] times, int n, int k) {
        // Node -> adjacent nodes
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();

        // Construct adjacency list
        for (int[] time : times) {
            int source = time[0];
            int dest = time[1];
            int weight = time[2];

            map.putIfAbsent(source, new HashMap<>());
            map.get(source).put(dest, weight);
        }

        // Create result array to keep track the shortest path
        int[] dis = new int[n + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[k] = 0; // 0 distance from source node to itself

        // BFS for Dijkstra's algo.
        Queue<int[]> q = new LinkedList();
        q.add(new int[]{k, 0}); // Add the source

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curNode = cur[0];
            int curWeight = cur[1];
            
            // Iterate the adjacent nodes of the current node
            for (int next : map.getOrDefault(curNode, new HashMap<>()).keySet()) {
                int nextWeight = map.get(curNode).get(next);

                if (curWeight + nextWeight < dis[next]) {
                    dis[next] = curWeight + nextWeight;
                    q.add(new int[]{next, curWeight + nextWeight});
                }
            }
        }

        // Find the result
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            res = Math.max(res, dis[i]);
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}