Network delay time

A signal leaves node k and travels along directed, timed edges. How long until every node has heard it? Dijkstra from k, then take the largest distance.

The idea

The signal spreads along every edge at once, so each node hears it at the moment of its shortest-path distance from k. Dijkstra finds all of those distances. The whole network has heard the signal when the farthest node has, so the answer is the largest distance; if any node is never reached, it is -1.

Code

public int NetworkDelayTime(int[][] times, int n, int k) {
    var graph = new List<(int to, int w)>[n + 1];
    for (int i = 1; i <= n; i++) graph[i] = new();
    foreach (var t in times) graph[t[0]].Add((t[1], t[2]));
    var dist = new int[n + 1];
    Array.Fill(dist, int.MaxValue);
    dist[k] = 0;
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(k, 0);
    while (pq.TryDequeue(out int u, out int d)) {
        if (d > dist[u]) continue; // stale entry: u was already settled closer
        foreach (var (v, w) in graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.Enqueue(v, dist[v]);
            }
        }
    }
    int best = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == int.MaxValue) return -1; // the signal never reaches i
        best = Math.Max(best, dist[i]);
    }
    return best;
}

Tips

• The answer is the maximum of the shortest distances, not their sum: the signal travels down all edges in parallel.
• Try removing "4 5 3" from the edges: node 5 can no longer be reached, so the answer becomes -1.
• Edges are one-way. "1 2 4" lets the signal go from 1 to 2, never from 2 to 1.

In the .NET library

PriorityQueue<TElement, TPriority> (.NET 6+) has no decrease-key. Enqueue the node again with its better distance and skip the stale copy when it comes out (the d > dist[u] check).