LeetCode : 743. Network Delay Time

Dijkstra is O(ElogE), On worse case, O(N^2) as every node gets in the heap.
class Solution {
    class Edge {
        int v, w;
        Edge (int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public int networkDelayTime(int[][] times, int N, int K) {
        Set<Integer> set = new HashSet();

        ArrayList<Edge>[] adj = new ArrayList[N+1];
        for (int i = 0; i <= N; i++) adj[i] = new ArrayList();

        for (int[] t : times) adj[t[0]].add(new Edge(t[1], t[2]));

        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
        int[] distance = new int[N+1];
        Arrays.fill(distance, -1); // no need to check visited[]
        pq.add(new Edge(K, 0)); // start Node
        distance[K] = 0;

        while(!pq.isEmpty()) {
            Edge s = pq.remove();
            int hereNode = s.v;
            int hereTime = s.w; // u -> v
            set.add(hereNode);

            if(hereTime > distance[hereNode]) continue; // for optimization

            for (Edge t: adj[hereNode]) {
                int thereNode = t.v;
                int thereTime = distance[hereNode] + t.w; // full time to thereNode
                if (distance[thereNode] == -1 || thereTime < distance[thereNode]) {
                    distance[thereNode] = thereTime;
                    pq.add(new Edge(t.v, t.w));
                }
            }
        }

        if (set.size() != N) return -1;

        int max = 0;
        for (int d : distance) max = Math.max(max, d);
        return max;
    }
}
congr / world

LeetCode : 743. Network Delay Time #491
