Вопрос 20 из 31

Практика: графы и маршруты

Длиннейший путь в DAG: когда работает топологический порядок

От чтения к действию

А теперь — вы

Из S в T есть только пути весов−3 и−8. Пустой путь к T не разрешён. Каков максимальный вес?

Разберёмся в теме

В ориентированном ациклическом графе максимальную сумму весов пути из заданного старта находят одним проходом по топологическому порядку. Старту назначают ноль, недостижимым вершинам — специальное состояние минус бесконечность. При переходе выбирают большую достижимую сумму.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.