Python 3 | Different 4 Methods | No Explanation
Approach \#1. Dijkstra\npython\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        dp = [sys.maxsize] * n\
### Approach \\#1. Dijkstra\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        dp = [sys.maxsize] * n\n        dp[k-1] = 0\n        graph = collections.defaultdict(list)\n        for s, e, w in times:\n            graph[s].append((e, w))\n        visited = set()    \n        heap = [(0, k)]            \n        while heap:\n            cur, node = heapq.heappop(heap)\n            dp[node-1] = cur\n            if node not in visited:\n                visited.add(node)\n                n -= 1\n            for nei, w in graph[node]:\n                if dp[nei-1] > cur + w:\n                    dp[nei-1] = cur + w\n                    if nei not in visited:\n                        heapq.heappush(heap, (cur + w, nei))\n            if not n: return cur\n        return -1\n```\n### Approach \\#2. Floyd-Warshall \n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        dp = [[sys.maxsize] * n for _ in range(n)]        \n        graph = collections.defaultdict(list)\n        for s, e, w in times:\n            graph[s].append((e, w))\n            dp[s-1][e-1] = w\n            \n        for i in range(n):\n            dp[i][i] = 0\n            \n        for kk in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dp[i][kk] != sys.maxsize and dp[kk][j] != sys.maxsize:\n                        dp[i][j] = min(dp[i][j], dp[i][kk] + dp[kk][j])\n        ans = 0                    \n        for j in range(n):\n            ans = max(ans, dp[k-1][j])\n        return ans if ans != sys.maxsize else -1\n```\n### Approach \\#3. Bellman-Ford\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        dp = [sys.maxsize] * n\n        dp[k-1] = 0\n        \n        for _ in range(n-1):\n            for s, e, w in times:\n                if dp[e-1] > dp[s-1] + w:\n                    dp[e-1] = dp[s-1] + w\n                    \n        ans = 0                    \n        for i in range(n):\n            if i != k-1:\n                ans = max(ans, dp[i])\n        return ans if ans != sys.maxsize else -1\n```\n### Approach \\#4. SPFA (deque implementation)\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        dp = [sys.maxsize] * n\n        dp[k-1] = 0\n        graph = collections.defaultdict(list)\n        for s, e, w in times:\n            graph[s].append((e, w))\n            \n        dq = collections.deque([k])\n        visited = set([k])\n        while dq:\n            node = dq.popleft()\n            cost = dp[node-1]\n            visited.remove(node)\n            for nei, w in graph[node]:\n                if dp[nei-1] > cost + w:\n                    dp[nei-1] = cost + w\n                    if nei not in visited:\n                        visited.add(nei)\n                        dq.append(nei)\n        \n        ans = 0                    \n        for i in range(n):\n            if i != k-1:\n                ans = max(ans, dp[i])\n        return ans if ans != sys.maxsize else -1\n```
['Python', 'Python3']