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(ui, vi) are unique. (i.e., no multiple edges.)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.
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.
Time Complexity: O((N + E) log N), where E is the number of edges.
Space Complexity: O(N + E) for constructing the adjacency list.
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.
Java
JavaScript
Time Complexity: O(N * E).
Space Complexity: O(N).
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.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Network Delay Time - Dijkstra's algorithm - Leetcode 743 • NeetCode • 170,635 views views
Watch 9 more video solutions →Practice Network Delay Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor