# LeetCode 743: Network Delay Time

## Problem Restatement

We are given a directed weighted graph with `n` nodes labeled from `1` to `n`.

The input `times` contains directed edges:

```python
[u, v, w]
```

This means a signal can travel from node `u` to node `v` in `w` time.

A signal starts from node `k`.

We need to return the minimum time needed for all nodes to receive the signal.

If some node cannot receive the signal, return `-1`.

The official statement gives `times[i] = (ui, vi, wi)` as directed travel times and asks for the minimum time for all `n` nodes to receive the signal. If impossible, return `-1`. The constraints include `1 <= k <= n <= 100`, `times.length <= 6000`, and unique directed pairs.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `times`, `n`, and `k` |
| Output | Minimum time for all nodes to receive the signal |
| Graph type | Directed weighted graph |
| Node labels | `1` to `n` |
| Unreachable node | Return `-1` |

Example function shape:

```python
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    ...
```

## Examples

### Example 1

```python
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2
```

The signal starts at node `2`.

It reaches:

| Node | Time |
|---:|---:|
| 2 | 0 |
| 1 | 1 |
| 3 | 1 |
| 4 | 2 |

The last node receives the signal at time `2`.

So the answer is:

```python
2
```

### Example 2

```python
times = [[1, 2, 1]]
n = 2
k = 1
```

The signal starts at node `1`.

It reaches node `2` in time `1`.

So the answer is:

```python
1
```

### Example 3

```python
times = [[1, 2, 1]]
n = 2
k = 2
```

The signal starts at node `2`.

There is no outgoing edge from node `2`, so node `1` cannot receive the signal.

The answer is:

```python
-1
```

## First Thought: Try All Paths

One possible approach is to explore every path from `k`.

For each node, keep the smallest time found so far.

But a graph may have many possible paths. Trying paths naively can repeat a large amount of work.

We need a shortest path algorithm.

Because all edge weights are non-negative, Dijkstra's algorithm fits this problem.

## Key Insight

The time when a node receives the signal is the shortest path distance from `k` to that node.

The answer is not the sum of all shortest paths.

The signal spreads through the network. All edges can carry the signal outward as soon as their source receives it.

So after computing the shortest time to every node, the total delay is:

```python
max(shortest_time_to_each_node)
```

because the last node to receive the signal determines the total time.

If any node has no shortest time, it is unreachable.

## Algorithm

Build an adjacency list:

```python
graph[u] = [(v, w), ...]
```

Then run Dijkstra's algorithm from node `k`.

1. Create a min-heap containing `(0, k)`.
2. Create a dictionary `dist` for finalized shortest times.
3. While the heap is not empty:
   - Pop the pair with the smallest time.
   - If the node was already finalized, skip it.
   - Store its shortest time.
   - Push all outgoing neighbors with updated time.
4. If fewer than `n` nodes were finalized, return `-1`.
5. Otherwise, return the maximum finalized distance.

## Correctness

Dijkstra's algorithm always processes the not-yet-finalized node with the smallest known arrival time.

Because all edge weights are non-negative, once a node is popped from the heap for the first time, no later path can reach that node faster. Therefore the first popped time for each node is its true shortest signal arrival time.

The algorithm stores each node's finalized shortest time in `dist`. For each outgoing edge, it pushes the candidate arrival time for the neighbor. Thus every reachable path from `k` is represented by some heap candidate, and the shortest candidate for each node is eventually finalized.

If fewer than `n` nodes are finalized, at least one node is unreachable from `k`, so returning `-1` is correct.

Otherwise, every node has a shortest signal arrival time. Since the signal reaches all nodes by the time the slowest reachable node receives it, the required network delay is the maximum value in `dist`.

## Complexity

Let `V = n` and `E = len(times)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(E log E)` | Each edge can push a heap entry |
| Space | `O(V + E)` | Store graph, heap, and finalized distances |

This is often written as `O(E log V)` with a standard Dijkstra implementation.

## Implementation

```python
from collections import defaultdict
import heapq

class Solution:
    def networkDelayTime(
        self,
        times: list[list[int]],
        n: int,
        k: int,
    ) -> int:
        graph = defaultdict(list)

        for u, v, w in times:
            graph[u].append((v, w))

        heap = [(0, k)]
        dist = {}

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

            if node in dist:
                continue

            dist[node] = time

            for neighbor, weight in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(
                        heap,
                        (time + weight, neighbor),
                    )

        if len(dist) != n:
            return -1

        return max(dist.values())
```

## Code Explanation

We build the graph as an adjacency list:

```python
graph = defaultdict(list)

for u, v, w in times:
    graph[u].append((v, w))
```

Each edge is directed, so we only add `v` to `u`'s list.

The heap starts at the source node with time `0`:

```python
heap = [(0, k)]
```

The dictionary `dist` stores finalized shortest times:

```python
dist = {}
```

When we pop from the heap:

```python
time, node = heapq.heappop(heap)
```

we skip the node if it already has a finalized distance:

```python
if node in dist:
    continue
```

Otherwise, this is the shortest time to that node:

```python
dist[node] = time
```

Then we push candidate times for all outgoing neighbors:

```python
for neighbor, weight in graph[node]:
    if neighbor not in dist:
        heapq.heappush(
            heap,
            (time + weight, neighbor),
        )
```

At the end, all nodes must have been reached:

```python
if len(dist) != n:
    return -1
```

If so, the answer is the time of the slowest node:

```python
return max(dist.values())
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.networkDelayTime(
        [[2, 1, 1], [2, 3, 1], [3, 4, 1]],
        4,
        2,
    ) == 2

    assert s.networkDelayTime(
        [[1, 2, 1]],
        2,
        1,
    ) == 1

    assert s.networkDelayTime(
        [[1, 2, 1]],
        2,
        2,
    ) == -1

    assert s.networkDelayTime(
        [[1, 2, 5], [1, 3, 1], [3, 2, 1]],
        3,
        1,
    ) == 2

    assert s.networkDelayTime(
        [[1, 2, 0], [2, 3, 0]],
        3,
        1,
    ) == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Checks multi-edge propagation |
| Single reachable edge | Basic reachable case |
| Start cannot reach another node | Must return `-1` |
| Shorter indirect path | Confirms shortest path logic |
| Zero-weight edges | Valid because weights may be zero |