[Python] - DFS, BFS, Dijkstra, Bellman Ford, SPFA, Floyd Warshall
\nimport heapq\nfrom collections import deque\nfrom collections import defaultdict\n\n# """\n#  Uses simple DFS - Accepted\nclass Solution(object):\n    def net
```\nimport heapq\nfrom collections import deque\nfrom collections import defaultdict\n\n# """\n#  Uses simple DFS - Accepted\nclass Solution(object):\n    def networkDelayTime(self, times, N, K):\n        graph = defaultdict(list)\n        for u, v, w in times:\n            graph[u].append((v, w))\n        distance = {node: float("inf") for node in range(1, N + 1)}\n        self.DFS(graph, distance, K, 0)\n        totalTime = max(distance.values())\n        return totalTime if totalTime < float("inf") else -1\n\n    def DFS(self, graph, distance, node, elapsedTimeSoFar):\n        if elapsedTimeSoFar >= distance[node]:   # signal aalreaady reached to this node. so no need to explore for this node\n            return\n        distance[node] = elapsedTimeSoFar\n        for neighbour, time in sorted(graph[node]):\n            self.DFS(graph, distance, neighbour, elapsedTimeSoFar + time)\n# """\n\n\n# """\n#  Uses simple BFS - Accepted\nclass Solution:\n    def networkDelayTime(self, times, N, K):\n        elapsedTime, graph, queue = [0] + [float("inf")] * N, defaultdict(list), deque([(0, K)])\n        for u, v, w in times:\n            graph[u].append((v, w))\n        while queue:\n            time, node = queue.popleft()\n            if time < elapsedTime[node]:\n                elapsedTime[node] = time\n                for v, w in graph[node]:\n                    queue.append((time + w, v))\n        mx = max(elapsedTime)\n        return mx if mx < float("inf") else -1\n# """\n\n\n\n# """\n# Dijkstra algorithm - Accepted\nclass Solution:\n    def networkDelayTime(self, times, N, K):\n        elapsedTime, graph, heap = [0] + [float("inf")] * N, defaultdict(list), [(0, K)] # it\'s a min-heap\n        for u, v, w in times:\n            graph[u].append((v, w))\n        while heap:\n            time, node = heapq.heappop()\n            if time < elapsedTime[node]:\n                elapsedTime[node] = time\n                for v, w in graph[node]:\n                    heapq.heappush(heap, (time + w, v))\n        mx = max(elapsedTime)\n        return mx if mx < float("inf") else -1\n# """\n\n\n\n# """\n# Original Bellman\u2013Ford algorithm - Accepted\nclass Solution:\n    def networkDelayTime(self, times, N, K):\n        distance = [float("inf") for _ in range(N)]\n        distance[K-1] = 0\n        for _ in range(N-1):\n            for u, v, w in times:\n                if distance[u-1] + w < distance[v-1]:\n                    distance[v-1] = distance[u-1] + w\n        return max(distance) if max(distance) < float("inf") else -1\n# """\n\n\n\n# """\n# Shortest Path Faster Algorithm (SPFA): An improvement of the Bellman\u2013Ford algorithm - Accepted\nclass Solution:\n    def networkDelayTime(self, times, N, K):\n        elapsedTime, graph, queue = [0] + [float("inf")] * N, defaultdict(list), deque([(0, K)])\n        elapsedTime[K] = 0\n        for u, v, w in times:\n            graph[u].append((v, w))\n        while queue:\n            time, node = queue.popleft()\n            for neighbour in graph[node]:\n                v, w = neighbour\n                if time + w < elapsedTime[v]:\n                    elapsedTime[v] = time + w\n                    queue.append((time + w, v))\n        mx = max(elapsedTime)\n        return mx if mx < float("inf") else -1\n# """\n\n\n\n\n\n# """\n#  Floyd Warshall - Accepted\nclass Solution:\n    def networkDelayTime(self, times, N, K):\n        elapsedTimeMatrix = [[float("inf") for _ in range(N)] for _ in range(N)]\n        for u, v, w in times:\n            elapsedTimeMatrix[u - 1][v - 1] = w\n        for i in range(N):                      #   Assigning 0 to the diagonal cells\n            elapsedTimeMatrix[i][i] = 0\n        for k in range(N):\n            for i in range(N):\n                for j in range(N):\n                    elapsedTimeMatrix[i][j] = min(elapsedTimeMatrix[i][j], elapsedTimeMatrix[i][k] + elapsedTimeMatrix[k][j])\n        mx = max(elapsedTimeMatrix[K - 1])\n        return mx if mx < float("inf") else -1\n# """\n\n```
['Depth-First Search', 'Breadth-First Search', 'Python']