Network Delay Time
Description
There are N
network nodes, labelled 1
to N
.
Given times
, a list of travel times as directed edges times[i] = (u, v, w)
, where u
is the source node, v
is the target node, and w
is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K
. How long will it take for all nodes to receive the signal? If it is impossible, return -1
.
Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
Note:
N
will be in the range[1, 100]
.K
will be in the range[1, N]
.The length of
times
will be in the range[1, 6000]
.All edges
times[i] = (u, v, w)
will have1 <= u, v <= N
and0 <= w <= 100
.
Solution
This problem is equivalent to the problem of finding the shortest paths between a node and all other nodes.
Dijkstra's algorithm
Running time: .
class Solution {
public:
int networkDelayTime(vector<vector<int>> ×, int N, int K) {
vector<vector<pair<int, int>>> neighbors(N + 1);
for (auto &t : times)
neighbors[t[0]].emplace_back(t[1], t[2]);
vector<int> dist(N + 1, INT_MAX);
dist[K] = 0;
auto comp = [&](int a, int b) {
return dist[a] > dist[b];
};
vector<int> heap(N);
for (int i = 0; i < N; ++i)
heap[i] = i + 1;
// Let V be the set of nodes.
// V - heap is the set of nodes to which the shortest paths from node K are known.
while (!heap.empty()) {
// extract min
make_heap(heap.begin(), heap.end(), comp);
int u = heap.front();
heap.front() = heap.back();
heap.pop_back();
// the closest node is unreachable
if (dist[u] == INT_MAX)
return -1;
for (auto &p : neighbors[u]) {
int v = p.first;
int w = p.second;
// O(1) time decrease key
dist[v] = min(dist[v], dist[u] + w);
}
}
return *max_element(dist.begin() + 1, dist.end());
}
};
Last updated