Djikstra : CLRS Implementation : O((E+V) Log V)
I came across several implementaiton of the Djikstra\'s while browsing through LeetCode disccuss. Most of the people have implemented Djikstra which is very sim
I came across several implementaiton of the Djikstra\'s while browsing through LeetCode disccuss. Most of the people have implemented Djikstra which is very similar to BFS but is different from the version mentioned in CLRS. Also, that implementation involves enqueuing element more than once in priority queue, though the later occurence of same element are tackled using maintaining a visited array.\n```\nclass Solution {\n       public int networkDelayTime(int[][] times, int N, int K) {\n        List<int[]>[] graph = new List[N+1];\n        for(int i=1;i<=N;i++)\n            graph[i]=new ArrayList<>();\n        for(int[] time : times)\n            graph[time[0]].add(new int[]{time[1],time[2]});\n        return djikstra(graph,N,K);\n    }\n    public int djikstra(List<int[]>[] graph, int n, int k){\n        int[] dist = new int[n+1];\n        Arrays.fill(dist,Integer.MAX_VALUE);\n        dist[k]=0;\n        TreeSet<Integer> q = new TreeSet<>((a,b) -> dist[a]!=dist[b]?dist[a]-dist[b]:a-b);//Sotring indices instead of distance, also when distances are same we compare based on index, it allows more than one vertex to have same distance.\n        for(int i=1;i<=n;i++)\n            q.add(i);\n        int res=0;\n        while(!q.isEmpty()){\n            int u = q.pollFirst();\n            res=Math.max(res,dist[u]);\n            for(int[] vertex : graph[u]){\n                int v = vertex[0];\n                int w = vertex[1];\n                if(dist[v]>dist[u]+w){\n                    q.remove(v);//removing and reinserting to ensure elements in treeset remain sorted\n                    dist[v]=dist[u]+w;\n                    q.add(v);\n                }\n            }\n\n        }\n        return res==Integer.MAX_VALUE?-1:res;\n    }\n}\n\n```\n\nComplexity Anaylysis : \nV : number of vertices, E : number of edges\n1. Leave aside the for loop inside while for the moment, remaining statement takes O(log V) for q.pollFirst() + Constant time, thsi poll operation happens at most V time => Time Complexity = O(v log v)\n2. Aggregate Analysis of inner for loop(inside while) : Here we are basically going through adjacency list of all vertices, that mean it will get executed E times, also each iteration will take O(log V) time.\n=>Time Complexity = O(E Log V)\n3. Overall Time Complexity : O((E+V) Log V))
[]