< Back




743. Network Delay Time

We're given a list of tuples representing edges in the times input of the format (u_i, v_i, w_i)
where u is the start node, v is the end node, and w is the weight of the edge. Given a starting
node, k, we're asked to find the minimum time it takes for all nodes in the graph to be reached. If
we can't reach all the nodes from the starting node, we return -1.

This is a common Dijkstra's algorithm question, super similar to DFS except edges are directional
and weighted. We construct a normal Dijkstra's algorithm search. Once the search is complete, we
take the maximum distance from the distances array. If float("inf") is still present in the
distances array, we know that not all nodes were reached, so we return -1. Otherwise, we return the
max distance.

The solution is as follows:


  from collections import defaultdict
  from heapq import heappush, heappop

  class Solution:
      def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
          distances = [float("inf") for _ in range(n)]
          distances[k - 1] = 0
          heap, edges = [(distances[k - 1], k - 1)], defaultdict(list)

          for u, v, w in times:
              edges[u - 1].append((v - 1, w))

          while heap:
              curr_dist, u = heappop(heap)

              if curr_dist > distances[u]:
                  continue

              neighbors = edges[u]

              for v, w in neighbors:
                  dist = curr_dist + w

                  if dist < distances[v]:
                      distances[v] = dist
                      heappush(heap, (dist, v))

          ans = max(distances)
          return ans if ans != float("inf") else -1


_ Time Complexity:

  O(n + elog(n)) - Where n is the number of nodes and e is the number of edges, this is the runtime
  of Dijkstra's algorithm. We also have to add the time complexity for n, as we select for the max
  distance in the distance array.

_ Space Complexity:

  O(n + e) - Building the adjaceny list takes e space. The distances array takes n space.