# 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).

```java
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
```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;
    }
}
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/743.-network-delay-time-dijkstra.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.