Сложность: 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 {
function maxProbability($n, $edges, $succProb, $start, $end) {
$maxProb = array_fill(0, $n, 0.0);
$maxProb[$start] = 1.0;
for ($i = 0; $i < $n - 1; $i++) {
$hasUpdate = false;
for ($j = 0; $j < count($edges); $j++) {
$u = $edges[$j][0];
$v = $edges[$j][1];
$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];
}
}Ставь 👍 и забирай 📚 Базу знаний