743. Network Delay Time - Explanation

Description

You are given a network of n directed nodes, labeled from 1 to n. You are also given times, a list of directed edges where times[i] = (ui, vi, ti).

ui is the source node (an integer from 1 to n)
vi is the target node (an integer from 1 to n)
ti is the time it takes for a signal to travel from the source to the target node (an integer greater than or equal to 0).

You are also given an integer k, representing the node that we will send a signal from.

Return the minimum time it takes for all of the n nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return -1 instead.

Example 1:

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

Output: 3

Example 2:

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

Output: -1

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(ElogV) time and O(V + E) space, where E is the number of edges and V is the number of vertices (nodes).

Hint 1

As we are given the source node and we need to find the minimum time to reach all nodes, this represents the shortest path from the source node to all nodes. Can you think of a standard algorithm to find the shortest path from a source to a destination? Maybe a heap-based algorithm is helpful.

Hint 2

We can use Dijkstra's algorithm to find the shortest path from a source to destination. We end up finding the shortest paths from the source to the nodes that we encounter in finding the destination. So, to find shortest path for all nodes from the source, we need to perform Dijkstra's algorithm until the heap in this algorithm becomes empty. How would you implement this?

Hint 3

We use a Min-Heap as we need to find the minimum time. We create an adjacency list for the given times (weighted edges). We also initialize an array dist[] of size n (number of nodes) which represents the distance from the source to all nodes, initialized with infinity. We put dist[source] = 0. Then we continue the algorithm. After the heap becomes empty, if we don't visit any node, we return -1; otherwise, we return the time.

Company Tags

Microsoft5 Netflix5 Amazon4 Bloomberg4 Google4 Meta4 Akuna Capital2 NVIDIA2 Salesforce2

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation (Adjacency List) - Building and traversing weighted directed graphs
Depth First Search (DFS) - Recursive graph traversal with path tracking
Shortest Path Algorithms - Understanding Dijkstra's, Bellman-Ford, and Floyd-Warshall concepts
Priority Queue / Min-Heap - Efficiently extracting minimum elements for Dijkstra's algorithm
Hash Maps - Storing distances and graph edges for quick lookups

1. Depth First Search

Intuition

We want to know how long it takes for a signal to reach all nodes starting from node k.

Using DFS, we try all possible paths from k and keep track of the minimum time needed to reach each node.

If we reach a node with a better (smaller) time, we update it.
If the current path is already worse than a known path, we stop exploring it (pruning).

After exploring all reachable paths:

The answer is the maximum time among all nodes (last node to receive the signal).
If any node is unreachable, return -1.

Algorithm

Build a graph from times where each edge has a weight.
Initialize a distance array with ∞ for all nodes.
Start dfs from node k with time 0.
During dfs:
- If current time ≥ known shortest time, stop.
- Otherwise, update the shortest time and continue dfs to neighbors.
After dfs:
- Take the maximum distance.
- If any distance is ∞, return -1, else return the maximum.

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

        dist = {node: float("inf") for node in range(1, n + 1)}

        def dfs(node, time):
            if time >= dist[node]:
                return

            dist[node] = time
            for nei, w in adj[node]:
                dfs(nei, time + w)

        dfs(k, 0)
        res = max(dist.values())
        return res if res < float('inf') else -1

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] time : times) {
            adj.computeIfAbsent(time[0],
            x -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }

        Map<Integer, Integer> dist = new HashMap<>();
        for (int i = 1; i <= n; i++) dist.put(i, Integer.MAX_VALUE);

        dfs(k, 0, adj, dist);
        int res = Collections.max(dist.values());
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private void dfs(int node, int time,
                     Map<Integer, List<int[]>> adj,
                     Map<Integer, Integer> dist) {
        if (time >= dist.get(node)) return;
        dist.put(node, time);
        if (!adj.containsKey(node)) return;
        for (int[] edge : adj.get(node)) {
            dfs(edge[0], time + edge[1], adj, dist);
        }
    }
}

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

        vector<int> dist(n + 1, INT_MAX);
        dfs(k, 0, adj, dist);

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

private:
    void dfs(int node, int time,
             unordered_map<int, vector<pair<int, int>>>& adj,
             vector<int>& dist) {
        if (time >= dist[node]) return;
        dist[node] = time;
        for (auto& [nei, w] : adj[node]) {
            dfs(nei, time + w, adj, dist);
        }
    }
};

class Solution {
    /**
     * @param {number[][]} times
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    networkDelayTime(times, n, k) {
        const adj = {};
        for (const [u, v, w] of times) {
            if (!adj[u]) adj[u] = [];
            adj[u].push([v, w]);
        }

        const dist = Array(n + 1).fill(Infinity);
        const dfs = (node, time) => {
            if (time >= dist[node]) return;
            dist[node] = time;
            if (!adj[node]) return;
            for (const [nei, w] of adj[node]) {
                dfs(nei, time + w);
            }
        };

        dfs(k, 0);
        const res = Math.max(...dist.slice(1));
        return res === Infinity ? -1 : res;
    }
}

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var adj = new Dictionary<int, List<int[]>>();
        foreach (var time in times) {
            if (!adj.ContainsKey(time[0])) {
                adj[time[0]] = new List<int[]>();
            }
            adj[time[0]].Add(new int[] { time[1], time[2] });
        }

        var dist = new Dictionary<int, int>();
        for (int i = 1; i <= n; i++) dist[i] = int.MaxValue;

        Dfs(k, 0, adj, dist);
        int res = dist.Values.Max();
        return res == int.MaxValue ? -1 : res;
    }

    private void Dfs(int node, int time,
                     Dictionary<int, List<int[]>> adj,
                     Dictionary<int, int> dist) {
        if (time >= dist[node]) return;
        dist[node] = time;
        if (!adj.ContainsKey(node)) return;
        foreach (var edge in adj[node]) {
            Dfs(edge[0], time + edge[1], adj, dist);
        }
    }
}

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val adj = HashMap<Int, MutableList<Pair<Int, Int>>>()
        for (time in times) {
            val (u, v, w) = time
            adj.computeIfAbsent(u) { mutableListOf() }.add(v to w)
        }

        val dist = HashMap<Int, Int>().apply {
            for (node in 1..n) {
                this[node] = Int.MAX_VALUE
            }
        }

        fun dfs(node: Int, time: Int) {
            if (time >= dist[node]!!) return
            dist[node] = time
            for ((nei, w) in adj[node] ?: emptyList()) {
                dfs(nei, time + w)
            }
        }

        dfs(k, 0)
        val res = dist.values.maxOrNull() ?: Int.MAX_VALUE
        return if (res == Int.MAX_VALUE) -1 else res
    }
}

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let mut adj: HashMap<usize, Vec<(usize, i32)>> = HashMap::new();
        for time in &times {
            adj.entry(time[0] as usize).or_default().push((time[1] as usize, time[2]));
        }
        let mut dist = vec![i32::MAX; n + 1];

        fn dfs(node: usize, time: i32, adj: &HashMap<usize, Vec<(usize, i32)>>, dist: &mut Vec<i32>) {
            if time >= dist[node] {
                return;
            }
            dist[node] = time;
            if let Some(neighbors) = adj.get(&node) {
                for &(nei, w) in neighbors {
                    dfs(nei, time + w, adj, dist);
                }
            }
        }

        dfs(k, 0, &adj, &mut dist);
        let res = *dist[1..=n].iter().max().unwrap();
        if res == i32::MAX { -1 } else { res }
    }
}

Time & Space Complexity

Time complexity: $O(V * E)$
Space complexity: $O(V + E)$

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

2. Floyd Warshall Algorithm

Intuition

We want the shortest time between every pair of nodes so that we can easily know how long it takes for the signal to reach all nodes starting from k.

Floyd–Warshall is an all-pairs shortest path algorithm:

It repeatedly tries to improve the shortest path between every (i, j) by allowing an intermediate node mid.
After processing all intermediates, dist[i][j] stores the shortest time from i to j.

Once all shortest paths are known:

Look at the row corresponding to the starting node k.
The maximum value in that row is the time when the last node receives the signal.
If any node is unreachable (distance = ∞), return -1.

Algorithm

Create a dist matrix initialized with ∞.
Set dist[u][v] = w for every directed edge (u → v) with weight w.
Set dist[i][i] = 0 for all nodes.
For each node mid:
- For every pair (i, j), update
  dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j])
Take the maximum distance from node k to all nodes.
If the maximum is ∞, return -1; otherwise return it.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        inf = float('inf')
        dist = [[inf] * n for _ in range(n)]

        for u, v, w in times:
            dist[u-1][v-1] = w
        for i in range(n):
            dist[i][i] = 0

        for mid in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j])

        res = max(dist[k-1])
        return res if res < inf else -1

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int inf = Integer.MAX_VALUE / 2;
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], inf);
            dist[i][i] = 0;
        }

        for (int[] time : times) {
            int u = time[0] - 1, v = time[1] - 1, w = time[2];
            dist[u][v] = w;
        }

        for (int mid = 0; mid < n; mid++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dist[i][j] = Math.min(dist[i][j],
                                          dist[i][mid] + dist[mid][j]);

        int res = Arrays.stream(dist[k-1]).max().getAsInt();
        return res == inf ? -1 : res;
    }
}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        int inf = INT_MAX / 2;
        vector<vector<int>> dist(n, vector<int>(n, inf));

        for (int i = 0; i < n; i++)
            dist[i][i] = 0;

        for (auto& time : times) {
            int u = time[0] - 1, v = time[1] - 1, w = time[2];
            dist[u][v] = w;
        }

        for (int mid = 0; mid < n; mid++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dist[i][j] = min(dist[i][j],
                                     dist[i][mid] + dist[mid][j]);

        int res = *max_element(dist[k-1].begin(), dist[k-1].end());
        return res == inf ? -1 : res;
    }
};

class Solution {
    /**
     * @param {number[][]} times
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    networkDelayTime(times, n, k) {
        const inf = Infinity;
        const dist = Array.from({ length: n }, () => Array(n).fill(inf));

        for (let i = 0; i < n; i++) {
            dist[i][i] = 0;
        }

        for (const [u, v, w] of times) {
            dist[u - 1][v - 1] = w;
        }

        for (let mid = 0; mid < n; mid++)
            for (let i = 0; i < n; i++)
                for (let j = 0; j < n; j++)
                    dist[i][j] = Math.min(
                        dist[i][j],
                        dist[i][mid] + dist[mid][j],
                    );

        const res = Math.max(...dist[k - 1]);
        return res === inf ? -1 : res;
    }
}

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        int inf = int.MaxValue / 2;
        int[,] dist = new int[n, n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = i == j ? 0 : inf;
            }
        }

        foreach (var time in times) {
            int u = time[0] - 1, v = time[1] - 1, w = time[2];
            dist[u, v] = w;
        }

        for (int mid = 0; mid < n; mid++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dist[i, j] = Math.Min(dist[i, j],
                                          dist[i, mid] + dist[mid, j]);

        int res = Enumerable.Range(0, n).Select(i => dist[k-1, i]).Max();
        return res == inf ? -1 : res;
    }
}

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val inf = (Int.MAX_VALUE / 2).toInt()
        val dist = Array(n) { IntArray(n) { inf } }

        for (i in 0 until n) {
            dist[i].fill(inf)
            dist[i][i] = 0
        }

        for (time in times) {
            val (u, v, w) = time
            dist[u - 1][v - 1] = w
        }

        for (mid in 0 until n) {
            for (i in 0 until n) {
                for (j in 0 until n) {
                    dist[i][j] = minOf(dist[i][j], dist[i][mid] + dist[mid][j])
                }
            }
        }

        val maxDelay = dist[k - 1].maxOrNull()
        return if (maxDelay == inf) -1 else maxDelay!!
    }
}

class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        let inf = Int.max / 2
        var dist = Array(repeating: Array(repeating: inf, count: n), count: n)

        for time in times {
            let u = time[0] - 1, v = time[1] - 1, w = time[2]
            dist[u][v] = w
        }
        for i in 0..<n {
            dist[i][i] = 0
        }

        for mid in 0..<n {
            for i in 0..<n {
                for j in 0..<n {
                    dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j])
                }
            }
        }

        let res = dist[k - 1].max()!
        return res >= inf ? -1 : res
    }
}

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
        let n = n as usize;
        let inf = i32::MAX / 2;
        let mut dist = vec![vec![inf; n]; n];

        for i in 0..n {
            dist[i][i] = 0;
        }
        for time in &times {
            let (u, v, w) = (time[0] as usize - 1, time[1] as usize - 1, time[2]);
            dist[u][v] = w;
        }

        for mid in 0..n {
            for i in 0..n {
                for j in 0..n {
                    dist[i][j] = dist[i][j].min(dist[i][mid] + dist[mid][j]);
                }
            }
        }

        let res = *dist[k as usize - 1].iter().max().unwrap();
        if res == inf { -1 } else { res }
    }
}

Time & Space Complexity

Time complexity: $O(V ^ 3)$
Space complexity: $O(V ^ 2)$

Where $V$ is the number of vertices.

3. Bellman Ford Algorithm

Intuition

We want the shortest time for a signal to reach every node starting from node k.

Bellman–Ford works by:

Relaxing (updating) all edges repeatedly.
Each relaxation tries to improve the shortest distance to a node using one more edge.
After n - 1 rounds, all shortest paths are guaranteed to be found (because the longest simple path has at most n - 1 edges).

Once distances are finalized:

The maximum distance tells us when the last node receives the signal.
If any node is still unreachable (∞), return -1.

Algorithm

Initialize a distance array dist of size n with ∞.
Set dist[k - 1] = 0 (source node).
Repeat n - 1 times:
- For every edge (u → v, w):
  - If dist[u] + w < dist[v], update dist[v].
Find the maximum value in dist.
If the maximum is ∞, return -1; otherwise return it.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[k - 1] = 0
        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u - 1] + w < dist[v - 1]:
                    dist[v - 1] = dist[u - 1] + w
        max_dist = max(dist)
        return max_dist if max_dist < float('inf') else -1

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k - 1] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int[] time : times) {
                int u = time[0] - 1, v = time[1] - 1, w = time[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        int maxDist = Arrays.stream(dist).max().getAsInt();
        return maxDist == Integer.MAX_VALUE ? -1 : maxDist;
    }
}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0;

        for (int i = 0; i < n - 1; ++i) {
            for (const auto& time : times) {
                int u = time[0] - 1, v = time[1] - 1, w = time[2];
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

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

class Solution {
    /**
     * @param {number[][]} times
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    networkDelayTime(times, n, k) {
        let dist = new Array(n).fill(Infinity);
        dist[k - 1] = 0;

        for (let i = 0; i < n - 1; i++) {
            for (const [u, v, w] of times) {
                if (dist[u - 1] + w < dist[v - 1]) {
                    dist[v - 1] = dist[u - 1] + w;
                }
            }
        }

        const maxDist = Math.max(...dist);
        return maxDist === Infinity ? -1 : maxDist;
    }
}

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
        dist[k - 1] = 0;

        for (int i = 0; i < n - 1; i++) {
            foreach (var time in times) {
                int u = time[0] - 1, v = time[1] - 1, w = time[2];
                if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        int maxDist = dist.Max();
        return maxDist == int.MaxValue ? -1 : maxDist;
    }
}

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val dist = IntArray(n) { Int.MAX_VALUE }
        dist[k - 1] = 0

        for (i in 0 until n - 1) {
            for (time in times) {
                val (u, v, w) = time
                if (dist[u - 1] != Int.MAX_VALUE && dist[u - 1] + w < dist[v - 1]) {
                    dist[v - 1] = dist[u - 1] + w
                }
            }
        }

        val maxDist = dist.maxOrNull()
        return if (maxDist == Int.MAX_VALUE) -1 else maxDist!!
    }
}

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut dist = vec![i32::MAX; n];
        dist[k as usize - 1] = 0;

        for _ in 0..n - 1 {
            for time in &times {
                let (u, v, w) = (time[0] as usize - 1, time[1] as usize - 1, time[2]);
                if dist[u] != i32::MAX && dist[u] + w < dist[v] {
                    dist[v] = dist[u] + w;
                }
            }
        }

        let max_dist = *dist.iter().max().unwrap();
        if max_dist == i32::MAX { -1 } else { max_dist }
    }
}

Time & Space Complexity

Time complexity: $O(V * E)$
Space complexity: $O(V)$

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

4. Shortest Path Faster Algorithm

Intuition

SPFA (Shortest Path Faster Algorithm) is an optimized version of Bellman–Ford.

Instead of relaxing all edges every time, we:

Only re-process nodes whose distance was actually improved
Use a queue to propagate distance updates efficiently

Whenever a node’s shortest time decreases, its neighbors might also get a shorter path — so we push that node into the queue.

This avoids unnecessary work and is usually much faster in practice.

Algorithm

Build an adjacency list from times.
Initialize dist for all nodes as ∞.
Set dist[k] = 0 and push (k, 0) into a queue.
While the queue is not empty:
- Pop (node, time)
- If time > dist[node], skip it (outdated path)
- For each neighbor:
  - If time + weight < dist[neighbor]:
    - Update dist[neighbor]
    - Push (neighbor, newTime) into the queue
Take the maximum value in dist.
If any node is unreachable (∞), return -1; otherwise return the max time.

class Solution:
    def networkDelayTime(self, times, n, k):
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))

        dist = {node: float("inf") for node in range(1, n + 1)}
        q = deque([(k, 0)])
        dist[k] = 0

        while q:
            node, time = q.popleft()
            if dist[node] < time:
                continue
            for nei, w in adj[node]:
                if time + w < dist[nei]:
                    dist[nei] = time + w
                    q.append((nei, time + w))

        res = max(dist.values())
        return res if res < float('inf') else -1

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

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

        queue<pair<int, int>> q;
        q.emplace(k, 0);

        while (!q.empty()) {
            auto [node, time] = q.front();
            q.pop();
            if (dist[node] < time) continue;
            for (const auto& [nei, w] : adj[node]) {
                if (time + w < dist[nei]) {
                    dist[nei] = time + w;
                    q.emplace(nei, time + w);
                }
            }
        }

        int res = 0;
        for (const auto& [node, time] : dist) {
            res = max(res, time);
        }
        return res == INT_MAX ? -1 : res;
    }
};

class Solution {
    /**
     * @param {number[][]} times
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    networkDelayTime(times, n, k) {
        const adj = {};
        for (let i = 1; i <= n; i++) adj[i] = [];
        for (const [u, v, w] of times) {
            adj[u].push([v, w]);
        }

        const dist = {};
        for (let i = 1; i <= n; i++) dist[i] = Infinity;
        dist[k] = 0;

        const q = new Queue([[k, 0]]);

        while (!q.isEmpty()) {
            const [node, time] = q.pop();
            if (dist[node] < time) continue;
            for (const [nei, w] of adj[node]) {
                if (time + w < dist[nei]) {
                    dist[nei] = time + w;
                    q.push([nei, time + w]);
                }
            }
        }

        let res = Math.max(...Object.values(dist));
        return res === Infinity ? -1 : res;
    }
}

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val adj = HashMap<Int, MutableList<IntArray>>()
        for (i in 1..n) adj[i] = mutableListOf()
        for (time in times) {
            adj[time[0]]?.add(intArrayOf(time[1], time[2]))
        }
        val dist = HashMap<Int, Int>()
        for (i in 1..n) dist[i] = Int.MAX_VALUE
        dist[k] = 0

        val q: Queue<IntArray> = LinkedList()
        q.offer(intArrayOf(k, 0))

        while (q.isNotEmpty()) {
            val (node, time) = q.poll()
            if (dist[node]!! < time) continue
            adj[node]?.forEach { (nextNode, weight) ->
                if (time + weight < dist[nextNode]!!) {
                    dist[nextNode] = time + weight
                    q.offer(intArrayOf(nextNode, time + weight))
                }
            }
        }

        val res = dist.values.maxOrNull() ?: Int.MAX_VALUE
        return if (res == Int.MAX_VALUE) -1 else res
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$ in average case, $O(V * E)$ in worst case.
Space complexity: $O(V + E)$

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

5. Dijkstra's Algorithm

Intuition

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.

Algorithm

Build an adjacency list from times.
Use a min-heap initialized with (0, k) (time, node).
Maintain a visited set to avoid reprocessing nodes.
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.
If all n nodes are visited, return the maximum time used.
Otherwise, return -1 (some nodes are unreachable).

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

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> edges = new HashMap<>();
        for (int[] time : times) {
            edges.computeIfAbsent(time[0],
            key -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
                                       Comparator.comparingInt(a -> a[0]));
        minHeap.offer(new int[]{0, k});

        Set<Integer> visited = new HashSet<>();
        int t = 0;
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int w1 = curr[0], n1 = curr[1];
            if (visited.contains(n1)) {
                continue;
            }
            visited.add(n1);
            t = w1;

            if (edges.containsKey(n1)) {
                for (int[] next : edges.get(n1)) {
                    int n2 = next[0], w2 = next[1];
                    if (!visited.contains(n2)) {
                        minHeap.offer(new int[]{w1 + w2, n2});
                    }
                }
            }
        }

        return visited.size() == n ? t : -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;
    }
};

/**
 * const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
 */

class Solution {
    /**
     * @param {number[][]} times
     * @param {number} n
     * @param {number} k
     * @return {number}
     */
    networkDelayTime(times, n, k) {
        const edges = new Map();
        for (let i = 1; i <= n; i++) {
            edges.set(i, []);
        }
        for (const [u, v, w] of times) {
            edges.get(u).push([v, w]);
        }

        const minHeap = new MinPriorityQueue((entry) => entry[0]);
        minHeap.enqueue([0, k]);

        const visit = new Set();
        let t = 0;

        while (!minHeap.isEmpty()) {
            const [w1, n1] = minHeap.dequeue();
            if (visit.has(n1)) continue;
            visit.add(n1);
            t = w1;

            for (const [n2, w2] of edges.get(n1)) {
                if (!visit.has(n2)) {
                    minHeap.enqueue([w1 + w2, n2]);
                }
            }
        }

        return visit.size === n ? t : -1;
    }
}

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var edges = new Dictionary<int, List<int[]>>();
        foreach (var time in times) {
            if (!edges.ContainsKey(time[0])) {
                edges[time[0]] = new List<int[]>();
            }
            edges[time[0]].Add(new int[] { time[1], time[2] });
        }

        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(k, 0);

        var dist = new Dictionary<int, int>();
        for (int i = 1; i <= n; i++) {
            dist[i] = int.MaxValue;
        }
        dist[k] = 0;

        while (pq.Count > 0) {
            // Correctly using TryDequeue to get node and its distance
            if (pq.TryDequeue(out int node, out int minDist)) {
                if (minDist > dist[node]) {
                    continue;
                }

                if (edges.ContainsKey(node)) {
                    foreach (var edge in edges[node]) {
                        var next = edge[0];
                        var weight = edge[1];
                        var newDist = minDist + weight;
                        if (newDist < dist[next]) {
                            dist[next] = newDist;
                            pq.Enqueue(next, newDist);
                        }
                    }
                }
            }
        }

        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == int.MaxValue) return -1;
            result = Math.Max(result, dist[i]);
        }

        return result;
    }
}

type Edge struct {
    node, weight int
}

func networkDelayTime(times [][]int, n int, k int) int {
    edges := make(map[int][]Edge)
    for _, time := range times {
        u, v, w := time[0], time[1], time[2]
        edges[u] = append(edges[u], Edge{node: v, weight: w})
    }

    pq := priorityqueue.NewWith(func(a, b interface{}) int {
        return utils.IntComparator(a.(Edge).weight, b.(Edge).weight)
    })
    pq.Enqueue(Edge{node: k, weight: 0})

    visited := make(map[int]bool)
    t := 0

    for !pq.Empty() {
        item, _ := pq.Dequeue()
        edge := item.(Edge)
        node, time := edge.node, edge.weight

        if visited[node] {
            continue
        }
        visited[node] = true
        t = time

        for _, next := range edges[node] {
            if !visited[next.node] {
                pq.Enqueue(Edge{node: next.node, weight: time + next.weight})
            }
        }
    }

    if len(visited) == n {
        return t
    }
    return -1
}

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        val edges = HashMap<Int, MutableList<Pair<Int, Int>>>()
        for ((u, v, w) in times) {
            edges.computeIfAbsent(u) { mutableListOf() }.add(Pair(v, w))
        }

        val minHeap = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
        minHeap.offer(Pair(0, k))
        val visited = HashSet<Int>()
        var t = 0

        while (minHeap.isNotEmpty()) {
            val (time, node) = minHeap.poll()
            if (node in visited) continue
            visited.add(node)
            t = time

            edges[node]?.forEach { (nextNode, weight) ->
                if (nextNode !in visited) {
                    minHeap.offer(Pair(time + weight, nextNode))
                }
            }
        }

        return if (visited.size == n) t else -1
    }
}

struct Item: Comparable {
    let weight: Int
    let node: Int

    static func < (lhs: Item, rhs: Item) -> Bool {
        return lhs.weight < rhs.weight
    }
}

class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        var edges = [Int: [(Int, Int)]]()
        for time in times {
            let u = time[0], v = time[1], w = time[2]
            edges[u, default: []].append((v, w))
        }

        var minHeap = Heap<Item>()
        minHeap.insert(Item(weight: 0, node: k))
        var visit = Set<Int>()
        var t = 0

        while !minHeap.isEmpty {
            let item = minHeap.removeMin()
            let w1 = item.weight
            let n1 = item.node

            if visit.contains(n1) {
                continue
            }
            visit.insert(n1)
            t = w1

            if let neighbors = edges[n1] {
                for (n2, w2) in neighbors {
                    if !visit.contains(n2) {
                        minHeap.insert(Item(weight: w1 + w2, node: n2))
                    }
                }
            }
        }
        return visit.count == n ? t : -1
    }
}

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut edges: HashMap<usize, Vec<(usize, i32)>> = HashMap::new();
        for time in &times {
            edges.entry(time[0] as usize).or_default().push((time[1] as usize, time[2]));
        }

        let mut min_heap = BinaryHeap::new();
        min_heap.push(Reverse((0i32, k as usize)));
        let mut visited = HashSet::new();
        let mut t = 0;

        while let Some(Reverse((w1, n1))) = min_heap.pop() {
            if !visited.insert(n1) {
                continue;
            }
            t = w1;
            if let Some(neighbors) = edges.get(&n1) {
                for &(n2, w2) in neighbors {
                    if !visited.contains(&n2) {
                        min_heap.push(Reverse((w1 + w2, n2)));
                    }
                }
            }
        }

        if visited.len() == n { t } else { -1 }
    }
}

Time & Space 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.

Common Pitfalls

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.