Efficient O(E log V) Python Dijkstra min heap with explanation
Good video to visualize what\'s happening in Dijkstra with minimal fuss https://www.youtube.com/watch?v=pVfj6mxhdMw\n\nPython implementation details:\n\n1. Cons
Good video to visualize what\'s happening in Dijkstra with minimal fuss https://www.youtube.com/watch?v=pVfj6mxhdMw\n\nPython implementation details:\n\n1. Construct adjacency list representation of a directional graph using a defaultdict of dicts\n2. Track visited vertices in a set\n3. Track known distances from K to all other vertices in a dict. Initialize this with a 0 to K.\n4. Use a `min_dist` heapq to maintain minheap of (distance, vertex) tuples. Initialize with (0,K). \n\nMain algorithm:\n1. While the `min_dist` is not empty, pop vertices in the order of minimal `cur_dist` , skip visited\n2. Visit the current vertex and check if any of its unvisited neighbors\' known `distances` can be improved. This is the case if `this_dist` is less than `distances[neighbor]`. \n3. Update the known distances and add new shorter distances onto the `min_dist` min heap if above is true.\n3. If we have not visited all of the nodes in the graph, we need to return -1 per problem statement\n4. Our answer is the largest known distance to any node from K\n\nThere is no efficient find method in a min heap. Whenever a new shorter distance to a vertex becomes known, we push onto the `min_dist` heap. This will result in duplicate vertices being on the min queue. Use `visited` set to skip duplicates in constant time. \n\nThis approach is not very space efficient for dense graphs because we will have O(|E|) items on the `min_dist` queue. However, this will allow for log |E| = 2 log |V| lookups of the next minimum distance edge to process.\n\nTime complexity: O(|E| log |E| ) = O(|E| 2 log |V|) = O(|E| log |V|)\n\n\n```\n    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        \n        graph = collections.defaultdict(dict)\n        \n        for frm, to, cost in times:\n            graph[frm][to] = cost\n        \n        distances = { i: float("inf") for i in range(1, N+1)}\n        distances[K] = 0\n        min_dist = [(0,K)]\n        visited = set()\n\n        while min_dist:\n            \n            cur_dist, cur = heapq.heappop(min_dist)\n            if cur in visited: continue\n            visited.add(cur)    \n            \n            for neighbor in graph[cur]:\n                if neighbor in visited: continue\n                this_dist = cur_dist + graph[cur][neighbor]\n                if this_dist  < distances[neighbor]:\n                    distances[neighbor] = this_dist\n                    heapq.heappush(min_dist, (this_dist, neighbor))\n            \n        if len(visited) != len(distances): return -1\n        return distances[max(distances,key=distances.get)]\n```
[]