loading

Network Delay Time — Step-by-Step Visualization

mediumLeetCode #743GraphBreadth-First SearchShortest PathHeap (Priority Queue)

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_i, v_i, w_i)`, where `u_i` is the source node, `v_i` is the target node, and `w_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.

Algorithm Pattern

Dijkstra's Algorithm (Shortest Path)

Key Idea

This is a classic 'Single Source Shortest Path' problem. Since edge weights are non-negative, Dijkstra's algorithm is ideal. We maintain a min-priority queue of `(time, node)` pairs, always visiting the node with the smallest cumulative time first. When we visit a node, we 'relax' all its neighbors by updating their shortest paths if a quicker way is found.

Step-by-Step Approach

  1. Build an adjacency list from `times`.
  2. Initialize `minDist = {node: infinity}` and set `minDist[k] = 0`.
  3. Initialize a min-heap with `[(0, k)]`.
  4. While the heap is not empty:
  5. Pop `(w1, n1)` from heap.
  6. If `w1 > minDist[n1]`, skip (already found a better path).
  7. For each neighbor `(n2, w2)` of `n1`:
  8. If `w1 + w2 < minDist[n2]`:
  9. `minDist[n2] = w1 + w2`.
  10. Push `(minDist[n2], n2)` to heap.
  11. Return `max(minDist.values())` if all nodes visited, else `-1`.

Common Gotchas

  • The labels are 1-indexed (1 to n).
  • If a node is unreachable, the signal doesn't reach everyone, so return -1.
  • Heaps always provide the shortest path first in Dijkstra.

Related Problems

← All problems