Network Delay Time

Problem

https://leetcode.com/problems/network-delay-time/

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u:sub:`i`, v:sub:`i`, w:sub:`i`), where u:sub:`i` is the source node, v:sub:`i` is the target node, and w:sub:`i` is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

image1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

  • 1 <= k <= n <= 100

  • 1 <= times.length <= 6000

  • times[i].length == 3

  • 1 <= u:sub:`i`, v:sub:`i`<= n

  • u:sub:`i`!= v:sub:`i`

  • 0 <= w:sub:`i`<= 100

  • All the pairs (u:sub:`i`, v:sub:`i`) are unique. (i.e., no multiple edges.)

Pattern

Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Approaches

Code

import heapq
from collections import defaultdict


def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for [u, v, time] in times:
        graph[u].append((v, time))

    dist = {u: float("inf") for u in range(1, n + 1)}
    dist[k] = 0

    heap = [(0, k)]

    while heap:
        time, v = heapq.heappop(heap)

        for neighbor, w in graph[v]:
            next_time = time + w
            if next_time < dist[neighbor]:
                dist[neighbor] = next_time
                heapq.heappush(heap, (next_time, neighbor))

    result = max(dist.values())
    return result if result < float("inf") else -1

Test

>>> from network_delay_time__dijkstra import networkDelayTime
>>> networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)
2
>>> networkDelayTime([[1,2,1]], 2, 1)
1
>>> networkDelayTime([[1,2,1]], 2, 2)
-1
network_delay_time__dijkstra.networkDelayTime(times: list[list[int]], n: int, k: int) → int