Description
給定一個無向加權圖，邊的權重是成功通過的機率。求從
start到end的最大成功機率路徑。若不可達回傳0。
Example:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 Output: 0.25
Intuition#
最大機率路徑 = 最短路徑的變體，用最大堆的 Dijkstra，乘積替代加法。
- 路徑的總機率是各段機率的乘積
- 求最大機率等同於求「最短路徑」，但用最大堆且鬆弛條件改為乘法
- 因為機率在 0~1 之間，乘積單調遞減，類似 Dijkstra 的性質
Approaches#
1: Bellman-Ford#
- 概念: 用 Bellman-Ford 反覆鬆弛所有邊，找最大機率
- 時間複雜度:
O(V * E) - 空間複雜度:
O(V)
class Solution {
fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
val prob = DoubleArray(n)
prob[start] = 1.0
repeat(n - 1) {
var updated = false
for (i in edges.indices) {
val (u, v) = edges[i]
val p = succProb[i]
if (prob[u] * p > prob[v]) {
prob[v] = prob[u] * p
updated = true
}
if (prob[v] * p > prob[u]) {
prob[u] = prob[v] * p
updated = true
}
}
if (!updated) return@repeat
}
return prob[end]
}
}⭐2: Dijkstra（最大堆）#
- 概念: 用最大堆的 Dijkstra，每次取出機率最大的節點，更新鄰居機率
- 時間複雜度:
O(E log V) - 空間複雜度:
O(V + E)
class Solution {
fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
val graph = Array(n) { mutableListOf<Pair<Int, Double>>() }
for (i in edges.indices) {
val (u, v) = edges[i]
graph[u].add(v to succProb[i])
graph[v].add(u to succProb[i])
}
val prob = DoubleArray(n)
prob[start] = 1.0
val pq = java.util.PriorityQueue<Pair<Int, Double>>(compareByDescending { it.second })
pq.add(start to 1.0)
while (pq.isNotEmpty()) {
val (node, p) = pq.poll()
if (node == end) return p
if (p < prob[node]) continue
for ((next, edgeProb) in graph[node]) {
val newProb = p * edgeProb
if (newProb > prob[next]) {
prob[next] = newProb
pq.add(next to newProb)
}
}
}
return 0.0
}
}🔑 Takeaways#
- Pattern: 最短路徑變體 – 最大化乘積等同於最小化負對數和
- 關鍵技巧: 將 Dijkstra 的最小堆改為最大堆，加法改為乘法，比較方向反轉；機率在 [0,1] 保證乘積單調遞減