743. Network Delay Time

Medium

Description

有 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#

單源最短路徑問題 – 用 Dijkstra 找從 k 到所有節點的最短距離，取最大值。

訊號到達所有節點的時間 = 從源點到最遠節點的最短路徑
所有邊權為正，適合用 Dijkstra 演算法
最終答案是所有最短距離中的最大值

Approaches#

1: Bellman-Ford#

概念: 鬆弛所有邊 n-1 次，得到從源點到所有節點的最短距離
時間複雜度: O(V * E)
空間複雜度: 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)

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 用於非負權重圖
關鍵技巧: if (d > dist[u]) continue 跳過已有更短路徑的節點（lazy deletion）；答案是所有最短距離的最大值