Network Delay Time
Problem Description
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 <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
Solve it on LeetCode
Approaches
1. Dijkstra's Algorithm
Intuition:
Dijkstra’s algorithm is a classic approach to find the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. By using a priority queue, we can efficiently choose the next node to process based on the smallest known distance.
Steps:
- Graph Representation: We first represent the graph using an adjacency list where each node points to its neighbors along with the time taken to reach them.
- Priority Queue (Min-Heap): Initialize a min-heap that will store elements as pairs of (time, node). The heap will prioritize nodes with smaller times.
- Distance Table: Create a distance table initialized with infinity (
Integer.MAX_VALUE) values to represent the shortest time (distance) from sourceKto each node. Set the distance to the source nodeKas 0. - Processing Nodes:
- While the priority queue is not empty, remove the node with the smallest time.
- For each neighbor of the current node, calculate the new time to reach that neighbor.
- If this new time is smaller than the previously recorded time in the distance table, update the table and add the neighbor to the priority queue.
- Finding the Result: The result is the maximum value from the distance table. If there's any node that remains at infinity, it means it's unreachable from the source
K.
Code:
- Time Complexity:
O(E log V), whereEis the number of edges andVis the number of vertices, due to the heap operations. - Space Complexity:
O(V + E), for storing the graph and the distance table.
2. Bellman-Ford Algorithm
Intuition:
The Bellman-Ford algorithm is another method to compute the shortest paths from a single source node to all other nodes in a graph, and it can handle negative weights. It repetitively relaxes all edges, updating the shortest paths.
Steps:
- Initialize Distance Array: Create a distance array with all nodes initially set to infinity (
Integer.MAX_VALUE), except for the source nodeKwhich is set to 0. - Relax Edges N-1 Times:
- For each edge from
utovwith weightw, if the current distance toupluswis less than the distance tov, update the distance tov. - Checking for Negative Cycles: (Not required for this problem since edge weights are non-negative)
- Run the relaxation step once more to check for improvements, which indicate negative cycles. For this problem, it can be skipped as all weights are positive.
- Determine the Result: Find the maximum time in the distance array. If all nodes are reachable, return this maximum time; otherwise, return
-1.
Code:
- Time Complexity:
O(V * E), as each of theVvertices requiresEedge relaxations. - Space Complexity:
O(V), as we only maintain a simple distance array.