Network Delay Time

Practice Link

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] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi 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:

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

Key Idea#

Finding the shortest path from a single source to all other nodes in a weighted directed graph.

Why plain BFS doesn't work#

It's tempting to BFS level by level from k and add up the largest edge weight at each level. That breaks for two reasons:

• Levels count hops, not time. With k→A (1), A→B (1) and k→B (10), BFS reaches B at level 1 with time 10, but the real shortest time is 2 (via A). A path with more edges can be faster.
• Without a visited/distance check, nodes are re-enqueued on every path. On a cycle the queue never empties, and counting "nodes found" overcounts nodes reached by multiple paths.

Dijkstra's Algorithm#

Every node receives the signal at the moment the shortest path from k reaches it, so the answer is the maximum of the shortest distances from k to every node. If any node is unreachable, the answer is -1. This is a textbook single-source shortest-path problem with non-negative weights, which is exactly what Dijkstra solves.

1. Build an adjacency list src → {dest, weight}.
2. Initialise dist[] to INT_MAX and set dist[k] = 0.
3. Use a min-heap of {time, node}. Pop the smallest time; if it's larger than dist[node], it's a stale entry, so skip it.
4. Relax each outgoing edge: if currTime + w < dist[next], update dist[next] and push it.
5. After the heap empties, scan nodes 1..n. Any dist[i] == INT_MAX means node i never got the signal, so return -1. Otherwise return the maximum dist[i].

Dry run on Example 1 (k = 2):

Max of dist = 2.

In Example 3 (k = 2), node 2 has no outgoing edges, so dist[1] stays INT_MAX and the answer is -1.

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int,int>>> adjList(n);
        for(int i=0;i<times.size();i++){
            int src = times[i][0];
            int dest = times[i][1];
            int wt = times[i][2];

            adjList[src].push_back({dest, wt});
        }

        vector<int> dist(n+1, INT_MAX);
        dist[k] = 0;

        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, k});

        while(!pq.empty()){
            auto [currTime, currNode] = pq.top();
            pq.pop();

            if(currTime > dist[currNode])
                continue;

            for(auto [nextNode, t]: adjList[currNode]){
                if(currTime + t < dist[nextNode]){
                    dist[nextNode] = currTime + t;
                    pq.push({dist[nextNode], nextNode});
                }
            }
        }

        int timeTaken = 0;
        for(int i=1;i<=n;i++){
            if(dist[i]==INT_MAX)
                return -1;

            timeTaken = max(timeTaken, dist[i]);
        }

        return timeTaken;
    }
};

Time Complexity: O(E log V) — each edge relaxation may push onto the heap, and each heap operation costs O(log V).

Space Complexity: O(V + E) — adjacency list, dist[] array, and the heap.

Follow Up#

Since the weights are small and non-negative, how would your approach change if the graph were extremely dense versus very sparse?#

LeetCode's constraints are 1 <= n <= 100, times.length <= 6000 and 0 <= wi <= 100, so the weights are small integers. That opens up three choices depending on how dense the graph is:

Sparse graph — keep the heap. Each node has only a few edges, so the heap stays small and O(E log V) is close to linear. Use an adjacency list to keep memory at O(V + E).

Dense graph — drop the heap. When E ≈ V², the heap version becomes O(V² log V), and the heap fills up with outdated entries. It's faster to keep a visited[] array and, at each step, scan all V nodes to pick the closest unvisited one. That's V picks × V scans = O(V²), with no log factor and no extra heap memory. An adjacency matrix also fits well here, since most cells are filled anyway.

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<int>> w(n + 1, vector<int>(n + 1, INT_MAX));
    for (auto& t : times) w[t[0]][t[1]] = t[2];

    vector<int> dist(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    dist[k] = 0;

    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;

        if (dist[u] == INT_MAX) break;      // remaining nodes are unreachable
        visited[u] = true;

        for (int v = 1; v <= n; v++)
            if (w[u][v] != INT_MAX && dist[u] + w[u][v] < dist[v])
                dist[v] = dist[u] + w[u][v];
    }

    int ans = *max_element(dist.begin() + 1, dist.end());
    return ans == INT_MAX ? -1 : ans;
}

Small integer weights — use buckets instead of a heap. No shortest distance can be larger than (V − 1) × C. So instead of a heap, keep an array of buckets where bucket[d] holds the nodes at tentative distance d, and walk through the buckets from d = 0 upward. Inserting and removing a node are both O(1), which gives O(E + V·C) overall and doesn't depend on density. With C = 100 and V = 100, that's at most about 10,000 buckets. If the weights were only 0 or 1, this becomes 0-1 BFS with a deque: push to the front for weight 0 and to the back for weight 1.