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.)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.
C++
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.
JavaScript
Time Complexity: O(N * E).
Space Complexity: O(N).
| 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). |
Network Delay Time - Dijkstra's algorithm - Leetcode 743 • NeetCode • 134,100 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