-
Notifications
You must be signed in to change notification settings - Fork 0
125 — Network Delay Time
LeetCode 743 · Medium. There are n network nodes labeled 1 to n. times[i] = [ui, vi, wi] is a directed edge from ui to vi taking wi time. A signal is sent from node k. Return the minimum time for the signal to reach every node, or -1 if some node is unreachable.
"Time for a signal to reach every node" is really "the shortest path from k to each other node, then take the worst (longest) of those shortest paths" — because the whole network only finishes receiving the signal when its slowest-to-reach member finally gets it. So this reduces to a single-source shortest path problem: compute the shortest distance from k to everyone, and the answer is the maximum of those distances (or -1 if any node's distance is still infinite).
Think of it like a rumor spreading through a group chat where each forward has a different delay — everyone eventually hears it, but "how long until everyone knows" is bottlenecked by whoever's chain of forwards is slowest, not fastest.
"Minimum time/cost from a single source to reach every other node, edges have non-negative weights" is the direct cue for Dijkstra's algorithm — repeatedly expand the closest not-yet-finalized node, using a min-heap to always know which unvisited node is currently nearest.
Bellman-Ford: relax every edge, n - 1 times over. No priority queue, no notion of "process the closest node first" — just brute-force repetition until distances stop improving (which is guaranteed within n - 1 rounds for a graph with no negative cycles).
func networkDelayTimeBruteForce(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
var dist = Array(repeating: Int.max, count: n + 1)
dist[k] = 0
for _ in 0..<(n - 1) {
for edge in times {
let u = edge[0], v = edge[1], w = edge[2]
if dist[u] != Int.max && dist[u] + w < dist[v] {
dist[v] = dist[u] + w
}
}
}
var maxDist = 0
for node in 1...n {
if dist[node] == Int.max { return -1 }
maxDist = max(maxDist, dist[node])
}
return maxDist
}
// smoke test
print(networkDelayTimeBruteForce([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) // 2
print(networkDelayTimeBruteForce([[1,2,1]], 2, 2)) // -1Big-O: O(V · E) — V - 1 full passes over every edge, each pass potentially improving multiple distances.
Dijkstra's algorithm with a min-heap: always expand the currently-closest unfinalized node next, so once a node is popped with its final distance, that distance is guaranteed correct and never revisited.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
var adjacency = Array(repeating: [(to: Int, weight: Int)](), count: n + 1)
for edge in times {
adjacency[edge[0]].append((to: edge[1], weight: edge[2]))
}
var dist = Array(repeating: Int.max, count: n + 1)
dist[k] = 0
var heap = Heap<(dist: Int, node: Int)>(sort: { $0.dist < $1.dist })
heap.insert((dist: 0, node: k))
while let current = heap.extract() {
guard current.dist == dist[current.node] else { continue } // stale heap entry
for edge in adjacency[current.node] {
let newDist = current.dist + edge.weight
if newDist < dist[edge.to] {
dist[edge.to] = newDist
heap.insert((dist: newDist, node: edge.to))
}
}
}
let farthest = dist[1...n].max()!
return farthest == Int.max ? -1 : farthest
}
// smoke test
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) // 2
print(networkDelayTime([[1,2,1]], 2, 1)) // 1
print(networkDelayTime([[1,2,1]], 2, 2)) // -1Big-O: O((V + E) log V) — every node is extracted from the heap once, and every edge may trigger one O(log V) heap insert. O(V + E) space for the adjacency list and heap.
Bellman-Ford and Dijkstra both repeatedly relax edges (if dist[u] + w < dist[v], improve dist[v]) until nothing improves — that relaxation step is identical. The difference is processing order. Bellman-Ford has no idea which node's distance is already final, so it must relax every edge, every round, V - 1 times, just to be safe. Dijkstra's min-heap always hands back the currently-nearest unfinalized node — and because all edge weights are non-negative, the nearest unfinalized node's distance can never be improved by a longer path later, so it's safe to treat as final and never touch again. That one guarantee (impossible with negative edges, which is exactly why Dijkstra requires non-negative weights and Bellman-Ford doesn't) is what turns V blind full passes into a single ordered sweep.
- Graphs — directed, weighted edges between network nodes; "minimum time to reach every node" is single-source shortest paths on that graph.
-
Heaps and Priority Queues — the same
Heap<T>used throughout this wiki, here as the min-heap that always yields the nearest unfinalized node next. - Greedy — Dijkstra is a greedy algorithm: always finalize the closest remaining node, and non-negative weights guarantee that local choice is never wrong in hindsight.
Network Delay Time is Dijkstra with an extra step at the end — find the shortest time to every node from the source, and the answer is however long the slowest one takes, or -1 if any node never hears the signal at all.
- Why is
guard current.dist == dist[current.node] else { continue }necessary in the optimal solution — what would go wrong (correctness-wise, not just efficiency-wise) if it were removed? - The optimal solution above uses lazy deletion: a stale heap entry is skipped by comparing distances, but no
visitedarray ever permanently marks a node as finalized, so a node can still be reprocessed if a later relaxation improves its distance. Rewrite it with an explicitvisitedarray instead (skip any popped node that's alreadyvisited, and never relax from it again — the more common textbook formulation). Then construct a small 4-node example with one negative edge, structured as a chain, where the lazy version above still returns the correct answer but yourvisited-array version doesn't. (Hint: you need a node to be finalized too early off a cheap direct edge, then have a negative edge reveal a cheaper route into it — and a further downstream node whose distance depends on that correction actually landing.) - Why does the answer require taking the maximum of all shortest distances from
k, rather than the sum or the count of reachable nodes?
⬅️ Previous: Min Cost to Connect All Points · Next: Swim in Rising Water ➡️