Просмотр исходного текста страницы Обсуждение:Несложно о сложности. Примеры алгоритмов/Задачи/ex-network-reliability

== Решение Савинова Николая, отличное от решения Бессарабова Никиты (которое неверно в том виде, в котором я понимаю задачу). ==



Насколько я понимаю, вероятность успешной доставки сообщения между 2 точками равна произведению вероятностей надежности ребер. Мы хотим максимизировать эту величину. Прологарифмируем произведение, получим сумму отрицательных \ln(p_e). Значит, нужно минимизировать сумму уже положительных -\ln(p_e). А с такой задачей Дейкстра справится. То есть запускаем его на графе с весами -\ln(p_e).
[[Category:На проверку]]