Network Delay Time - Solution & Explanation
Problem Statement
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
Constraints:
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Approach Overview
Problem Overview: A signal starts from node k and travels through a directed weighted graph. Each edge (u, v, w) represents a travel time w. The goal is to determine how long it takes for the signal to reach every node. If any node is unreachable, return -1. Otherwise return the maximum shortest-path distance from k to all nodes.
Approach 1: Dijkstra's Algorithm (Time: O(E log V), Space: O(V + E))
This problem is a classic shortest path scenario on a weighted directed graph with non‑negative edge weights. Build an adjacency list from the input edges, then run Dijkstra starting from node k. Maintain a distance array where dist[i] stores the shortest time to reach node i. Use a priority queue (min‑heap) to always process the node with the smallest known distance. For each popped node, iterate through its neighbors and relax edges by updating distances if current + weight is smaller. After processing all reachable nodes, the answer is the maximum value in the distance array. If any node still has infinite distance, the graph is disconnected and the result is -1.
Dijkstra works well because edge weights are non‑negative and we only need the shortest path from one source. The heap ensures we always expand the next closest node, keeping the algorithm efficient even for large graphs.
Approach 2: Bellman-Ford Algorithm (Time: O(V * E), Space: O(V))
The Bellman‑Ford algorithm computes shortest paths by repeatedly relaxing all edges. Initialize distances with infinity except the source node k. Then iterate n-1 times over the edge list. For each edge (u, v, w), update dist[v] = min(dist[v], dist[u] + w). Each iteration propagates shorter paths across the graph until the optimal distances stabilize.
This approach does not require a heap or adjacency list and works even when negative weights exist (though this problem doesn't include them). Its simplicity makes it easy to implement, but the O(V * E) complexity is significantly slower than Dijkstra for dense graphs. It still reliably solves the problem and is useful for understanding fundamental graph relaxation techniques.
Recommended for interviews: Dijkstra’s algorithm is the expected solution. Interviewers want to see that you recognize the problem as a single‑source shortest path on a weighted graph and immediately reach for a min‑heap based approach. Bellman‑Ford demonstrates understanding of edge relaxation and graph fundamentals, but Dijkstra shows stronger algorithmic optimization and is the standard answer.
Approach 1: Dijkstra's Algorithm
Dijkstra's Algorithm is effective for finding the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. By implementing a priority queue, we repeatedly select the node with the smallest tentative distance, update its neighboring nodes, and do this until all nodes have been processed.
The Python solution uses a priority queue (min-heap) to always expand the least cost node using the heapq module. It keeps track of each node’s shortest distance from the starting node. If not all nodes are reached, we return -1.
Complexity
Time Complexity: O((N + E) log N), where E is the number of edges.
Space Complexity: O(N + E) for constructing the adjacency list.
Approach 2: Bellman-Ford Algorithm
The Bellman-Ford Algorithm is efficient in handling negative edge weights, which doesn't apply here but showcases versatility in cyclical graphs. It operates by executing N-1 passes over each edge and updating the shortest paths stored for each node.
This Java approach utilizes the Bellman-Ford algorithm. The array holds the shortest path estimate where each pass attempts to update the shortest path based on the available edges. It completes in N-1 passes.
Code
Java
JavaScript
Complexity
Time Complexity: O(N * E).
Space Complexity: O(N).
Approach 3: Naive Dijkstra Algorithm
We define g[u][v] to represent the edge weight from node u to node v. If there is no edge between node u and node v, then g[u][v] = +infty.
We maintain an array dist, where dist[i] represents the shortest path length from node k to node i. Initially, we set all dist[i] to +infty, except for dist[k - 1] = 0. We define an array vis, where vis[i] indicates whether node i has been visited. Initially, we set all vis[i] to false.
Each time, we find the unvisited node t with the smallest distance, and then perform relaxation operations centered on node t. For each node j, if dist[j] > dist[t] + g[t][j], we update dist[j] = dist[t] + g[t][j].
Finally, we return the maximum value in dist as the answer. If the answer is +infty, it means there are unreachable nodes, and we return -1.
The time complexity is O(n^2 + m), and the space complexity is O(n^2). Here, n and m are the number of nodes and edges, respectively.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Heap-Optimized Dijkstra Algorithm
We can use a priority queue (heap) to optimize the naive Dijkstra algorithm.
We define g[u] to represent all adjacent edges of node u, and dist[u] to represent the shortest path length from node k to node u. Initially, we set all dist[u] to +infty, except for dist[k - 1] = 0.
We define a priority queue pq, where each element is (d, u), representing the distance d from node u to node k. Each time, we take out the node (d, u) with the smallest distance from pq. If d > dist[u], we skip this node. Otherwise, we traverse all adjacent edges of node u. For each adjacent edge (v, w), if dist[v] > dist[u] + w, we update dist[v] = dist[u] + w and add (dist[v], v) to pq.
Finally, we return the maximum value in dist as the answer. If the answer is +infty, it means there are unreachable nodes, and we return -1.
The time complexity is O(m times log m + n), and the space complexity is O(n + m). Here, n and m$ are the number of nodes and edges, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm | Time Complexity: O((N + E) log N), where E is the number of edges. |
| Bellman-Ford Algorithm | Time Complexity: O(N * E). |
| Naive Dijkstra Algorithm | — |
| Heap-Optimized Dijkstra Algorithm | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm (Min Heap) | O(E log V) | O(V + E) | Best choice for weighted graphs with non‑negative edges. Efficient for typical interview and production scenarios. |
| Bellman-Ford Algorithm | O(V * E) | O(V) | Useful when negative weights may appear or when demonstrating edge relaxation fundamentals. |
Video Solution
Network Delay Time - Dijkstra's algorithm - Leetcode 743 • NeetCode • 180,206 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Network Delay Time easy or hard?
How to solve Network Delay Time in O(E log V)?
What is the best approach for Network Delay Time?
Is Network Delay Time asked at Google/Amazon/Meta?
What data structure is used in Network Delay Time?
What is the time complexity of Network Delay Time?
Network Delay Time Python or Java solution approach?
Ready to solve this problem?
Practice Network Delay Time with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor