有
n個網路節點，給定times[i] = [u, v, w]表示從u到v的訊號需要w時間。從節點k發出訊號，回傳所有節點收到訊號的最短時間。若有節點無法到達，回傳-1。
Example:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2
Intuition
TIP
單源最短路徑問題 — 用 Dijkstra 找從 k 到所有節點的最短距離，取最大值。
- 訊號到達所有節點的時間 = 從源點到最遠節點的最短路徑
- 所有邊權為正，適合用 Dijkstra 演算法
- 最終答案是所有最短距離中的最大值
Approaches
1. Bellman-Ford — O(V * E) / O(V)
- Idea: 鬆弛所有邊 n-1 次，得到從源點到所有節點的最短距離
- Time:
O(V * E) - Space:
O(V)
class Solution {
fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
val dist = IntArray(n + 1) { Int.MAX_VALUE }
dist[k] = 0
repeat(n - 1) {
for ((u, v, w) in times) {
if (dist[u] != Int.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w
}
}
}
val maxDist = (1..n).maxOf { dist[it] }
return if (maxDist == Int.MAX_VALUE) -1 else maxDist
}
}⭐ 2. Dijkstra（Priority Queue） — O(E log V) / O(V + E)
- Idea: 用最小堆每次取出距離最小的未確定節點，更新其鄰居距離
- Time:
O(E log V) - Space:
O(V + E)
class Solution {
fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
val graph = Array(n + 1) { mutableListOf<IntArray>() }
for ((u, v, w) in times) {
graph[u].add(intArrayOf(v, w))
}
val dist = IntArray(n + 1) { Int.MAX_VALUE }
dist[k] = 0
// [distance, node]
val pq = PriorityQueue<IntArray>(compareBy { it[0] })
pq.add(intArrayOf(0, k))
while (pq.isNotEmpty()) {
val (d, u) = pq.poll()
if (d > dist[u]) continue
for ((v, w) in graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w
pq.add(intArrayOf(dist[v], v))
}
}
}
val maxDist = (1..n).maxOf { dist[it] }
return if (maxDist == Int.MAX_VALUE) -1 else maxDist
}
}🔑 Takeaways
- Pattern: 單源最短路徑 — Dijkstra 用於非負權重圖
- Key trick:
if (d > dist[u]) continue跳過已有更短路徑的節點（lazy deletion）；答案是所有最短距離的最大值