Dijkstra's algorithm solution explanation (with Python 3)
Since the graph of network delay times is a weighted, connected graph (if the graph isn\'t connected, we can return -1) with non-negative weights, we can find t
Since the graph of network delay times is a weighted, connected graph (if the graph isn\'t connected, we can return -1) with non-negative weights, we can find the shortest path from root node K into any other node using Dijkstra\'s algorithm. If we want to find how long it will take for all nodes to receive the signal, we need to find the maximum of the shortest paths from node K to any other node. \n\nWe can do this by running dijkstra\'s algorithm starting with node K, and shortest path length to node K, 0. We can keep track of the lengths of the shortest paths from K to every other node in a set S, and if the length of S is equal to N, we know that the graph is connected (if not, return -1). We can then return the maximum of the shortest path lengths in S to get how long it will take for all nodes to receive the signal.\n\n```\ndef networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        graph = collections.defaultdict(list)\n        for (u, v, w) in times:\n            graph[u].append((v, w))\n            \n        priority_queue = [(0, K)]\n        shortest_path = {}\n        while priority_queue:\n            w, v = heapq.heappop(priority_queue)\n            if v not in shortest_path:\n                shortest_path[v] = w\n                for v_i, w_i in graph[v]:\n                    heapq.heappush(priority_queue, (w + w_i, v_i))\n                    \n        if len(shortest_path) == N:\n            return max(shortest_path.values())\n        else:\n            return -1\n```\n
['Queue', 'Heap (Priority Queue)', 'Ordered Set', 'Python', 'Python3']