Сложность: medium
Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].
Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.
Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.
Пример:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
👨💻 Алгоритм:
1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.
2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].
3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].
😎 Решение
class Solution {
func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
var maxProb = [Double](repeating: 0, count: n)
maxProb[start] = 1.0
for _ in 0..<n-1 {
var hasUpdate = false
for j in 0..<edges.count {
let u = edges[j][0]
let v = edges[j][1]
let pathProb = succProb[j]
if maxProb[u] * pathProb > maxProb[v] {
maxProb[v] = maxProb[u] * pathProb
hasUpdate = true
}
if maxProb[v] * pathProb > maxProb[u] {
maxProb[u] = maxProb[v] * pathProb
hasUpdate = true
}
}
if !hasUpdate {
break
}
}
return maxProb[end]
}
}Ставь 👍 и забирай 📚 Базу знаний