Network Delay Time

The problem

A network has n nodes, numbered 1 to n. Each entry of times is a one-way link [from, to, time]: a signal that is at the first node arrives at the second node that many time units later. The time is never negative. A signal starts at node k at time 0 and spreads along every link it can use, so each node receives it as early as any route allows. Return the time at which the last node receives the signal. If some node never receives it, return -1. A network of one node needs no time: return 0.

What to write

function solve(times: number[][], n: number, k: number): number

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

Output
2

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

Output
1

Constraints

Edge weights are nonnegative.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Link times are never negative, so going round in a circle never gets the signal anywhere sooner. A quickest route therefore never needs to pass through a node twice. Links work in one direction only, and a node with no route from k makes the answer -1.

2. Hint 2: Ask a smaller question

   Suppose you already know that the signal can be at node 3 at time 1, and a link from node 3 to node 4 takes 1. What does that tell you about node 4? And what should happen to that fact if you later find a quicker way to node 3?

3. Hint 3: Name the pattern

   A node gets the signal at the length of the shortest route from k, where every link has its own length. Links with different lengths plus a question about the quickest way are the signal for a weighted shortest path. This solution uses the Bellman-Ford algorithm: improve the known times link by link until nothing improves. Read the lesson on weighted shortest path.

4. Hint 4: State the invariant

   Every time stored for a node is the length of a real route from k, so it is never too small. After r full rounds over the links, the stored time is final for every node whose quickest route has r links or fewer.

5. Hint 5: Sketch the pseudocode

   Set every time to infinity and node k's to 0. Repeat n - 1 times: for each link [u, v, w], if time[u] + w is less than time[v], store that sum in time[v]. Stop early when a round changes nothing. Return the largest time among nodes 1 to n, or -1 if that is infinity.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Relax all edges with Bellman–Ford until distances stop changing. The largest shortest-path distance is the broadcast time.

The slow way

Follow every possible route from node k, adding up the link times on the way, and keep the smallest total with which each node was reached. It is correct if no route visits a node twice, but the number of routes explodes: ten nodes that are all linked to each other already have almost a million routes from one of them.

The insight

You do not need the routes, only the earliest time known for each node. If the signal can be at one node at some time, a link from there proves it can be at the link's other end that much later. Checking one link this way is called relaxing it. Relaxing all the links, round after round, until no time improves is the Bellman-Ford algorithm.

Step by step

1. Mark every node as not reached, except the start node at time 0. Infinity stands for not reached: any real time is smaller, so the first route found replaces it. The list has n + 1 slots because the nodes are numbered from 1.
2. Run up to n - 1 rounds, each one starting with nothing changed. Link times are never negative, so a quickest route never needs to visit a node twice: n - 1 links at most. Each round gets the times right for routes one link longer, so n - 1 rounds suffice.
3. Try every link to see if it brings the signal to its end sooner. This test is called relaxing the link. The time at the link's start plus the link's own time is a real arrival time at its end. If the start is not reached yet, that sum is infinity and nothing happens.
4. If it does, store the earlier time and note that a time changed. A node receives the signal at the earliest moment any route delivers it, so only the smallest time is worth keeping. The note tells the loop that another round may still find improvements.
5. A round that changes nothing means every time is final: stop early. The next round would try the same links against the same times and get the same result. So the times can never change again, and the remaining rounds can be skipped.
6. Return the latest arrival time, or -1 if some node was never reached. All nodes have the signal once the slowest node has it, so the answer is the largest time. A node that still holds infinity has no route from the start, which is the -1 case.

The same numbered steps are the comments in each solution.

function solve(times, n, k) {
  // 1. Mark every node as not reached, except the start node at time 0
  // Nodes are numbered from 1, so the list has n + 1 slots and slot 0 is unused.
  const dist = Array(n + 1).fill(Infinity);
  dist[k] = 0;
  // 2. Run up to n - 1 rounds, each one starting with nothing changed
  for (let i = 1; i < n; i++) {
    let changed = false;
    // 3. Try every link to see if it brings the signal to its end sooner
    for (const [u, v, w] of times)
      if (dist[u] + w < dist[v]) {
        // 4. If it does, store the earlier time and note that a time changed
        dist[v] = dist[u] + w;
        changed = true;
      }
    // 5. A round that changes nothing means every time is final: stop early
    if (!changed) break;
  }
  // 6. Return the latest arrival time, or -1 if some node was never reached
  // slice(1) leaves out the unused slot 0, which still holds Infinity.
  const max = Math.max(...dist.slice(1));
  return max === Infinity ? -1 : max;
}

function solve(times: number[][], n: number, k: number): number {
  // 1. Mark every node as not reached, except the start node at time 0
  // Nodes are numbered from 1, so the list has n + 1 slots and slot 0 is unused.
  const dist = Array(n + 1).fill(Infinity);
  dist[k] = 0;
  // 2. Run up to n - 1 rounds, each one starting with nothing changed
  for (let i = 1; i < n; i++) {
    let changed = false;
    // 3. Try every link to see if it brings the signal to its end sooner
    for (const [u, v, w] of times)
      if (dist[u] + w < dist[v]) {
        // 4. If it does, store the earlier time and note that a time changed
        dist[v] = dist[u] + w;
        changed = true;
      }
    // 5. A round that changes nothing means every time is final: stop early
    if (!changed) break;
  }
  // 6. Return the latest arrival time, or -1 if some node was never reached
  // slice(1) leaves out the unused slot 0, which still holds Infinity.
  const max = Math.max(...dist.slice(1));
  return max === Infinity ? -1 : max;
}

def solve(times, n, k):
    # 1. Mark every node as not reached, except the start node at time 0
    # Nodes are numbered from 1, so the list has n + 1 slots and slot 0 is unused.
    dist = [float("inf")] * (n + 1)
    dist[k] = 0
    # 2. Run up to n - 1 rounds, each one starting with nothing changed
    for _ in range(1, n):
        changed = False
        # 3. Try every link to see if it brings the signal to its end sooner
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                # 4. If it does, store the earlier time and note that a time changed
                dist[v] = dist[u] + w
                changed = True
        # 5. A round that changes nothing means every time is final: stop early
        if not changed:
            break
    # 6. Return the latest arrival time, or -1 if some node was never reached
    # dist[1:] leaves out the unused slot 0, which still holds infinity.
    longest = max(dist[1:])
    return -1 if longest == float("inf") else longest

Example 1, traced

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

Output
2

Why it works

A stored time always belongs to a real route, so it is never too small. After the first round the times are right for every node whose quickest route is one link long, after the second for two links, and so on. A quickest route needs at most n - 1 links, so n - 1 rounds are enough, and a round without a change proves the times are final.

Time and space

Time O(V E), extra space O(V). V is the number of nodes and E the number of links. There are at most V - 1 rounds, and each round tries all E links once: O(V E) time. The only thing stored is one time per node: O(V) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• One pass over the links is not enough: a link can only pass on a time its start node already has. With example 1's links in the opposite order, a single pass never reaches node 4 and returns -1.
• A node's first time is not always its earliest. With links [1,2,5], [1,3,1], [3,2,1], n = 3, k = 1, node 2 first gets 5, but the route through node 3 arrives at 2. Never lowering a time returns 5.
• Nodes are numbered from 1, so the list of times needs n + 1 slots. With only n slots, Python stops with an IndexError in example 1, and JavaScript quietly returns 1 instead of 2.

Pattern

Weighted shortest path. Builds on Rotting Oranges.

Keep going