743. Network Delay Time (dijkstra

dijkstra

Time complexity: O(Nlog(N) + E),

Space complexity: O(N + E)

• time: O(ElogE) in the heap implementation, as potentially every edge gets added to the heap.

• Space Complexity: O(N + E), the size of the graph (O(E)), plus the size of the other objects used (O(N).

class Solution {
    class Pair {
        int node;
        int time;
        Pair(int node, int time) {
            this.node = node;
            this.time = time;
        }
    }
    public int networkDelayTime(int[][] times, int n, int k) { // k: start
        Map<Integer, Set<Pair>> graph = buildGraph(times);
        Queue<Pair> queue = new PriorityQueue<>((a,b) -> a.time - b.time);
        queue.offer(new Pair(k, 0));
        Set<Integer> visited = new HashSet<>();
        
        int res = 0;
        while(!queue.isEmpty()){
            Pair cur = queue.remove();
            int curNode = cur.node;
            int curTime = cur.time;
            if(visited.contains(curNode)) {
                continue;
            }
            visited.add(curNode);
            
            res = curTime;
            n--;
            if(graph.containsKey(curNode)){
                for(Pair next : graph.get(curNode)){
                    queue.add(new Pair(next.node, curTime + next.time));
                }
            }
        }

        return n == 0 ? res : -1;
    }
    private Map<Integer, Set<Pair>> buildGraph(int[][] times) {
        Map<Integer, Set<Pair>> map = new HashMap<>();
        for (int[] time : times) {
            map.computeIfAbsent(time[0], s -> new HashSet<>()).add(new Pair(time[1], time[2]));
            // this q is single way
            //map.computeIfAbsent(edge[1], s -> new HashSet<>()).add(new Pair(edge[0], edge[2]));
        }
        return map;
    }
}

new version

because we use PQ, we poll the smallest path every time, so using visited is reasonable.

```java
class Solution {
    class Step {
        int nodeId;
        int time;
        Step(int nodeId, int time) {
            this.nodeId = nodeId;
            this.time = time;
        }
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<Step>> graph = buildGraph(times);

        Queue<Step> queue = new PriorityQueue<>((a, b) -> a.time - b.time);
        queue.offer(new Step(k, 0));
        Set<Integer> visited = new HashSet<>();

        while (!queue.isEmpty()) {
            Step curr = queue.poll();
            if (visited.contains(curr.nodeId)){
                continue;
            }
            visited.add(curr.nodeId);
            n--; // use this to control unreach case!
            if (n == 0) { // reach last point
                return curr.time;
            }
            if (graph.containsKey(curr.nodeId)) {
                for (Step s : graph.get(curr.nodeId)) {
                    queue.offer(new Step(s.nodeId, curr.time + s.time));
                }
            }
        }
        return -1;
    }
    private Map<Integer, List<Step>> buildGraph(int[][] times) { // Map<from, <to, time>>
        Map<Integer, List<Step>> map = new HashMap<>();
        for (int[] time : times) {
            map.putIfAbsent(time[0], new ArrayList<>());
            map.get(time[0]).add(new Step(time[1], time[2]));
        }
        return map;
    }
}
```