Python Bellman-Ford, SPFA, Dijkstra, Floyd, clean and easy to understand
Since the input is edges, it naturally occured to me to use Bellman-Ford. Of course we can process the edges and use SPFA (Shortest Path Faster Algorithm) and D
Since the input is edges, it naturally occured to me to use Bellman-Ford. Of course we can process the edges and use [SPFA](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm) (Shortest Path Faster Algorithm) and Dijkstra.\n\n**Bellman-Ford**\nTime: `O(VE)`\nSpace: `O(N)`\n\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        dist = [float("inf") for _ in range(N)]\n        dist[K-1] = 0\n        for _ in range(N-1):\n            for u, v, w in times:\n                if dist[u-1] + w < dist[v-1]:\n                    dist[v-1] = dist[u-1] + w\n        return max(dist) if max(dist) < float("inf") else -1\n```\n\n**SPFA**\nTime: average `O(E)`, worst `O(VE)`\nSpace: `O(V+E)`\n\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        dist = [float("inf") for _ in range(N)]\n        K -= 1\n        dist[K] = 0\n        weight = collections.defaultdict(dict)\n        for u, v, w in times:\n            weight[u-1][v-1] = w\n        queue = collections.deque([K])\n        while queue:\n            u = queue.popleft()\n            for v in weight[u]:\n                if dist[u] + weight[u][v] < dist[v]:\n                    dist[v] = dist[u] + weight[u][v]\n                    queue.append(v)\n        return max(dist) if max(dist) < float("inf") else -1\n```\n\n**Dijkstra**\nTime: `O(E+VlogV)`\nSpace: `O(V+E)`\n\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        weight = collections.defaultdict(dict)\n        for u, v, w in times:\n            weight[u][v] = w\n        heap = [(0, K)]\n        dist = {}\n        while heap:\n            time, u = heapq.heappop(heap)\n            if u not in dist:\n                dist[u] = time\n                for v in weight[u]:\n                    heapq.heappush(heap, (dist[u] + weight[u][v], v))\n        return max(dist.values()) if len(dist) == N else -1\n```\n\n**Floyd-Warshall**\nTime: `O(V^3)`\nSpace: `O(V^2)`\n\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:\n        dist = [[float("inf") for _ in range(N)] for _ in range(N)]\n        for u, v, w in times:\n            dist[u-1][v-1] = w\n        for i in range(N):\n            dist[i][i] = 0\n        for k in range(N):\n            for i in range(N):\n                for j in range(N):\n                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])\n        return max(dist[K-1]) if max(dist[K-1]) < float("inf") else -1\n```
[]