Network Delay Time

How it works

Dijkstra's Algorithm finds the shortest time from the source node k to all other nodes when all edge weights are non-negative.

The key idea:

• Always expand the node that currently has the smallest known time
• Once a node is picked from the min-heap, its shortest time is final
• Use a min-heap (priority queue) to always process the closest node next

By doing this, we gradually spread the signal in increasing order of time.

Steps

1. Build an adjacency list from times.
2. Use a min-heap initialized with (0, k) (time, node).
3. Maintain a visited set to avoid reprocessing nodes.
4. While the heap is not empty:
   • Pop the node with the smallest time.
   • If already visited, skip.
   • Mark it visited and update the current time.
   • Push all unvisited neighbors with updated times into the heap.
5. If all n nodes are visited, return the maximum time used.
6. Otherwise, return -1 (some nodes are unreachable).

Complexity

• Time complexity: O(E log V)
• Space complexity: O(V + E)

Where V is the number of vertices and E is the number of edges.

Things to watch for

Returning Max Instead of Checking Unreachable Nodes

The answer is the maximum time to reach any node, but only if all nodes are reachable. Some solutions return the maximum distance without first checking if any node remains at infinity. This returns an incorrect large value instead of -1 when nodes are unreachable.

Using 1-Based vs 0-Based Indexing

Nodes are numbered from 1 to n, not 0 to n-1. Mixing up indexing when building the adjacency list or distance array causes out-of-bounds errors or skipped nodes. Consistently use either 1-based arrays of size n+1 or subtract 1 from all node numbers.

Revisiting Nodes Without Proper Checks

In Dijkstra's algorithm, once a node is finalized (popped from the min-heap), its shortest distance is determined. Processing the same node again wastes time and can cause issues in some implementations. Always skip nodes that have already been visited or whose current distance exceeds the known shortest.

from typing import List
import collections
import heapq

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        edges = collections.defaultdict(list)
        for u, v, w in times:
            edges[u].append((v, w))

        minHeap = [(0, k)]
        visit = set()
        t = 0
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 in visit:
                continue
            visit.add(n1)
            t = w1

            for n2, w2 in edges[n1]:
                if n2 not in visit:
                    heapq.heappush(minHeap, (w1 + w2, n2))
        return t if len(visit) == n else -1

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int, int>>> edges;
        for (const auto& time : times) {
            edges[time[0]].emplace_back(time[1], time[2]);
        }

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

        set<int> visited;
        int t = 0;
        while (!minHeap.empty()) {
            auto curr = minHeap.top();
            minHeap.pop();
            int w1 = curr.first, n1 = curr.second;
            if (visited.count(n1)) {
                continue;
            }
            visited.insert(n1);
            t = w1;

            if (edges.count(n1)) {
                for (const auto& next : edges[n1]) {
                    int n2 = next.first, w2 = next.second;
                    if (!visited.count(n2)) {
                        minHeap.push({w1 + w2, n2});
                    }
                }
            }
        }

        return visited.size() == n ? t : -1;
    }
};