Network Delay Time

You send a signal from one computer in a network. The signal spreads to other computers along wires. Each wire takes some time. You want to know how long until every computer has the signal. This is really a shortest path question in disguise. So it is the perfect place to learn Dijkstra’s algorithm, which shows up in interviews all the time.

🎯 The Problem

You send a signal from one node. You must find how long until every node has it.

The rules:

• You get n nodes, numbered 1 to n.
• You get travel times. Each entry [u, v, w] means a signal goes from u to v in w time.
• The edges are one-way.
• The signal starts at node k.
• Return the time for the slowest node to receive it.
• If some node can never be reached, return -1.

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

Explanation: From node 2 the signal reaches node 1 in time 1,
node 3 in time 1, and node 4 in time 2. The slowest is 2.

The shortest time to reach a node is its shortest path from the start. A shortest path is the route with the smallest total cost. The answer is the largest shortest path among all nodes. Here is the network for the example.

🐢 Approach 1: Try Every Route (Brute Force)

The idea in one line: list every route from the start to each node and keep the shortest.

The idea:

• From the start, walk out along edges in every possible way.
• Record the total time of each full route to a node.
• For each node, keep its smallest route time.

Why it is weak:

• The number of routes explodes as the network grows.
• The same edges get walked again and again across routes.
• Far too slow on any real network.

Here is the route-relaxation code:

def network_delay_time(times, n, k):
    dist = [float("inf")] * (n + 1); dist[k] = 0
    for _ in range(n - 1):
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    ans = max(dist[1:])
    return -1 if ans == float("inf") else ans

🔁 Approach 2: Bellman-Ford (Better)

The idea in one line: relax every edge over and over until the distances stop improving.

The idea:

• Bellman-Ford keeps a best-known distance for every node.
• Relaxing an edge means: if going through it gives a shorter distance, update it.

How it works:

• Set the start distance to zero and the rest to infinity.
• Relax every edge once. Repeat that whole pass up to n - 1 times.
• After the passes settle, every distance is final.

Why pick it sometimes:

• It works even when edge weights are negative.

Why it is weak here:

• It relaxes every edge in every pass.
• That is O(V times E), more work than needed when all weights are positive.

Here is Bellman-Ford:

def network_delay_time(times, n, k):
    dist = [float("inf")] * (n + 1); dist[k] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w; changed = True
        if not changed: break
    ans = max(dist[1:])
    return -1 if ans == float("inf") else ans

⚡ Approach 3: Dijkstra’s Algorithm (Best)

The idea in one line: always settle the closest unsettled node next, using a min-heap.

The idea:

• Dijkstra’s algorithm finds the shortest path from one start to all nodes.
• A min-heap is a structure that hands you the smallest item quickly.

How it works:

• Set every distance to infinity, except the start at zero. Push the start into the heap.
• Pull the node with the smallest distance. That distance is now final.
• It is final because all weights are positive, so no later path can beat it.
• For each neighbor, if going through this node is shorter, update it and push it.
• Keep going until the heap is empty.
• The answer is the largest settled distance. If a node is still infinity, return -1.

Why it is fast:

• Each node settles once. Each edge is pushed once.
• Each heap step costs about log of its size, giving O(E log V).

Here is the order Dijkstra’s settles the nodes on the example, each with its final shortest time.

Steps to Solve

1. Build a map from each node to its list of [neighbor, time] edges.
2. Set every node’s distance to infinity, except the start node which is zero.
3. Push the start node into a min-heap with distance zero.
4. Pull the closest node. If you already settled it with a smaller distance, skip it.
5. For each neighbor, if going through this node is shorter, update it and push it.
6. When the heap is empty, take the largest distance. If any node is unreached, return -1.

#include <stdio.h>

#define INF 1000000000

int main(void) {
    int times[][3] = {{2,1,1},{2,3,1},{3,4,1}};
    int m = 3, n = 4, k = 2;

    int dist[5];
    int done[5];
    for (int i = 1; i <= n; i++) { dist[i] = INF; done[i] = 0; }
    dist[k] = 0;  // start node

    for (int c = 0; c < n; c++) {
        int u = -1;
        for (int i = 1; i <= n; i++) {        // closest unsettled node
            if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
        }
        if (dist[u] == INF) break;            // rest are unreachable
        done[u] = 1;
        for (int e = 0; e < m; e++) {         // relax edges out of u
            if (times[e][0] == u) {
                int v = times[e][1], w = times[e][2];
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) { answer = -1; break; }
        if (dist[i] > answer) answer = dist[i];
    }
    printf("%d\n", answer);
    return 0;
}

2

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
    vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
    int n = 4, k = 2;

    vector<vector<pair<int,int>>> graph(n + 1);  // node -> (neighbor, time)
    for (auto &t : times) graph[t[0]].push_back({t[1], t[2]});

    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, k});  // (distance, node)

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;            // stale entry
        for (auto &edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (d + w < dist[v]) {            // shorter path found
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) { answer = -1; break; }
        answer = max(answer, dist[i]);
    }
    cout << answer << endl;
    return 0;
}

2

import java.util.*;

public class Network {
    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4, k = 2;

        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] t : times) graph[t[0]].add(new int[]{t[1], t[2]});

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});  // (distance, node)

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (d > dist[u]) continue;        // stale entry
            for (int[] edge : graph[u]) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {        // shorter path found
                    dist[v] = d + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) { answer = -1; break; }
            answer = Math.max(answer, dist[i]);
        }
        System.out.println(answer);
    }
}

2

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))     # node -> (neighbor, time)

    dist = {}
    heap = [(0, k)]                 # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)  # closest unsettled node
        if u in dist:
            continue                # already settled
        dist[u] = d
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))

    if len(dist) < n:
        return -1                   # some node never reached
    return max(dist.values())       # slowest arrival


times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
print(network_delay_time(times, 4, 2))

2

function networkDelayTime(times, n, k) {
  const graph = {};
  for (const [u, v, w] of times) {
    if (!graph[u]) graph[u] = [];
    graph[u].push([v, w]); // node -> [neighbor, time]
  }

  const dist = {};
  const heap = [[0, k]]; // [distance, node]
  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]); // keep smallest at the front
    const [d, u] = heap.shift();      // closest unsettled node
    if (dist[u] !== undefined) continue;
    dist[u] = d;
    for (const [v, w] of graph[u] || []) {
      if (dist[v] === undefined) heap.push([d + w, v]);
    }
  }

  if (Object.keys(dist).length < n) return -1; // some node unreached
  return Math.max(...Object.values(dist));      // slowest arrival
}

const times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]];
console.log(networkDelayTime(times, 4, 2));

2

Let us read the Python version line by line and understand each choice.

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

We turn the edge list into an adjacency map. Adjacency map means each node points to the list of its direct neighbors and the time to reach them. This lets us find a node’s neighbors instantly instead of scanning all edges.

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

dist holds the final shortest time for each settled node. The heap starts with the start node k at distance zero. We store pairs as (distance, node) so the heap orders by distance first.

while heap:
    d, u = heapq.heappop(heap)
    if u in dist:
        continue
    dist[u] = d

We pop the closest unsettled node. If it is already in dist, we settled it earlier with a smaller distance, so we skip this stale copy. Otherwise this popped distance is its final shortest time. Because all weights are positive, nothing later can reach it faster.

for v, w in graph[u]:
    if v not in dist:
        heapq.heappush(heap, (d + w, v))

For each neighbor v not yet settled, we push a new candidate distance d + w. We do not remove old heap entries. Instead the if u in dist check above ignores any stale copies when they surface.

if len(dist) < n:
    return -1
return max(dist.values())

If we settled fewer nodes than n, some node was unreachable, so we return -1. Otherwise the answer is the largest shortest distance, which is the slowest node to get the signal.

⏱️ Time and Space Complexity

Let V be the number of nodes and E the number of edges. Dijkstra’s with a heap settles each node once and pushes each edge once. Each heap operation costs about log of its size. So the total time is O(E log V). The space holds the graph, the distances, and the heap, which is O(V + E). Bellman-Ford would be O(V times E), which is slower here.

🧩 Key Takeaways

• ✅ Network Delay Time is a shortest path problem, and the answer is the largest shortest path.
• ✅ Dijkstra’s algorithm settles the closest unsettled node first using a min-heap.
• ✅ A popped distance is final because all edge weights are positive.
• ✅ Skip stale heap entries by checking if a node is already settled.
• ✅ It runs in O(E log V) time, faster than Bellman-Ford for positive weights.

🚀 What’s Next?

• Cheapest Flights Within K Stops
• Swim in Rising Water