Информатика · объяснение и практика
Длиннейший путь в DAG: когда работает топологический порядок
Максимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.

В теме Графы и маршруты · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
В ориентированном ациклическом графе максимальную сумму весов пути из заданного старта находят одним проходом по топологическому порядку. Старту назначают ноль, недостижимым вершинам — специальное состояние минус бесконечность. При переходе выбирают большую достижимую сумму.
Фиксируем начало и смысл длины
Путь здесь оценивается суммой весов рёбер, а не числом вершин. Нужен конкретный старт: путь с большим весом в другой несвязанной части графа не является ответом на наш запрос. Ацикличность позволяет расположить вершины так, чтобы все предшественники были обработаны раньше следующей вершины.
Для старта допустим пустой путь веса ноль. Остальные вершины до обработки не имеют известного пути из старта. Если вместо специального недостижимого состояния присвоить им ноль, алгоритм разрешит начинать движение где угодно и тем самым решит другую задачу, особенно заметно при отрицательных весах.
Сравниваем отрицательные варианты
Пусть есть рёбра S→A с весом−4,S→B с весом−1,A→T с весом 2 и B→T с весом−5. Через A путь имеет сумму−2,через B —−6. Максимальный ответ равен−2,хотя он отрицателен. Ноль не является доступным путём из S в T.
Дополнительно пусть вершина D не достижима из S,но из неё ведёт ребро в T веса 100. Этот переход нельзя использовать как будто до D уже есть путь нулевой стоимости. Состояние недостижимости должно сохраняться при попытке продолжения, иначе получится выдуманный выгодный маршрут из неправильного начала.
Пример
Пути S→A→T и S→B→T имеют веса−2 и−6. Выбираем−2. Отдельное D→T веса 100 не учитываем, если до D из S пути нет.
Сравниваются только допустимые пути из заданного источника. Большой вес ребра не создаёт отсутствующий начальный участок.
Почему отрицательные веса не мешают порядку
При обработке ребра u→v проверяют кандидат d[u]+w и обновляют d[v],если кандидат больше текущего достижимого результата. Поскольку все предшественники u уже обработаны, возвращаться к ней из будущих вершин не понадобится. В этом рассуждении важна ацикличность, а не неотрицательность весов.
Если в графе есть циклы, такой проход не имеет прежнего обоснования. Вопрос о самом длинном простом пути и вопрос о неограниченном обходе положительного цикла требуют других условий. Даже для DAG программа должна отдельно контролировать переполнение или погрешность арифметики: правильная рекуррентная формула не делает любой числовой тип точным.
От чтения к действию
А теперь — вы
Частые вопросы
Можно всем вершинам сначала присвоить ноль?
Нет, если старт фиксирован. Это выдало бы недостижимым вершинам несуществующий путь и могло исказить отрицательные ответы.
Отрицательное ребро запрещает этот алгоритм?
Нет. Для DAG топологический порядок позволяет обработать и отрицательные веса; циклы — отдельная проблема.
Углублённый разбор
Какие рёбра обязательны во всех длиннейших путях DAG
Ребро может лежать на одном оптимальном пути и всё же не быть обязательным. Два счётчика — оптимальных префиксов и суффиксов — показывают, какие рёбра входят во все длиннейшие пути фиксированного запроса.
Перед началом: Длиннейший путь в DAG; Комбинаторное правило произведения.
Считайте только лучшие префиксы
В топологическом порядке храним максимальную достижимую длину dₛ[v] и число cₛ[v] префиксов этой длины. Для источника значения равны 0 и 1, для недостижимой вершины длина специальная, счётчик ноль. Если новое предложение длины лучше прежнего, счётчик заменяют на cₛ[u]. Если равно, прибавляют cₛ[u]. Худшее предложение не меняет ни длину, ни число оптимальных вариантов.
Обратный проход от цели даёт dₜ[v] и cₜ[v] для лучших суффиксов v→t. Отрицательные веса в DAG допустимы: важен порядок без циклов. При равных длинах складываются действительно разные пути, а не повторные чтения одного ребра. Если параллельные рёбра различимы, каждое имеет собственный идентификатор и отдельный вклад.
Через оптимальное ребро варианты перемножаются
Пусть D=dₛ[t], C=cₛ[t]. Ребро u→v участвует в оптимальной семье только при dₛ[u]+w+dₜ[v]=D и достижимых концах. В DAG любой лучший префикс до u совместим с любым лучшим суффиксом от v: общая вершина создала бы направленный цикл через выбранное ребро. Поэтому число оптимальных путей через него равно cₛ[u]cₜ[v].
Ребро обязательно тогда и только тогда, когда оно оптимально и это произведение равно C. Равенство длин отвечает на вопрос «хотя бы один путь», равенство счётчиков — на вопрос «каждый путь». Нулевой временной резерв работы или вершины сам по себе не делает все соседние рёбра обязательными при нескольких критических ветвях.
Нужны точные целые количества
Количество путей может быстро расти. Счёт по модулю подходит некоторым задачам, но не даёт точного сертификата обязательности: разные большие числа могут иметь одинаковый остаток. При сравнении произведения с общим C используйте точные целые либо отдельно доказанные границы, исключающие неоднозначность.
Если цель недостижима, C=0 не означает, что все рёбра с нулевым произведением обязательны. Семья путей пуста, и исходный вопрос должен получить специальный статус отсутствия маршрута. Для маленького графа независимым контролем является перечисление всех путей, отбор максимальной длины и пересечение их множеств рёбер.
Критические ветви и общий хвост
Условие. Рёбра s→a:2,s→b:2,a→c:3,b→c:3,c→t:1,s→t:4. Какие рёбра обязательны во всех длиннейших s→t путях?
- Префиксы дают dₛ(a)=dₛ(b)=2, dₛ(c)=5, dₛ(t)=6. В c приходят два лучших префикса, значит cₛ(c)=cₛ(t)=2.
- Из c в t имеется один лучший суффикс. Из a и b также по одному; из s лучших суффиксов два.
- Через c→t проходит cₛ(c)cₜ(t)=2·1=2 оптимальных пути, то есть вся семья C=2.
- Через каждое ребро одной ветви проходит только один лучший путь. Прямое s→t имеетдлину 4<6 ивообще не оптимально.
Ответ. Единственное обязательное ребро c→t; оптимальных путей два, оба длины 6.
Проверка. Длиннейшие пути s,a,c,t и s,b,c,t имеют пересечение рёбер ровно{c→t}. Прямой путь s,t короче и не влияет на обязательность внутри оптимальной семьи.
Где легко ошибиться. Принадлежность хотя бы одному лучшему пути слабее обязательности во всех. Для второго вывода сравнивают точные количества, а не только длины или остатки счётчиков по модулю.
Проверьте понимание
Вопросы к этой главе
Могут ли два критических ребра быть альтернативными?
Да. В разных ветвях оба могут входить в длиннейшие пути, но каждый отсутствует в другой ветви. Обязательность возникает только после проверки всей оптимальной семьи.
Почему произведение не завышает число путей?
В DAG префикс и суффикс выбранного ребра не могут пересечься в дополнительной вершине: это создало бы цикл. Поэтому их независимые сочетания дают разные допустимые пути без повторений.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James Aspnes, Yale: TopologicalSort
Авторские университетские заметки: вебом проверены определение порядка DAG и линейная стоимость обычной сортировки. Критерий единственности и обновления при добавлении ребра доказаны в данной главе отдельно.
Перенос длительности вершины на отдельное ребро
Когда длительность относится к вершине, обычная сумма рёбер не считает её автоматически. Разделение каждой задачи на вход и выход переносит длительность на отдельное ребро и сохраняет все допустимые цепочки зависимостей.
Перед началом: DAG зависимостей; Взвешенный путь.
У каждой задачи появляется обязательный внутренний переход
Для задачи v длительности τᵥ создают вершины v_in и v_out и ребро v_in→v_out веса τᵥ. Зависимость u→v заменяют ребром u_out→v_in веса 0. Любой маршрут, выполняющий задачу, обязан пройти её внутреннее ребро и начислить длительность ровно один раз. Нулевые рёбра выражают только ожидание предпосылок, а не дополнительную работу.
Обратное соответствие также важно: любой путь преобразованного графа с полными задачами сжимается в цепочку исходных задач. Внутренние переходы и зависимости чередуются, поэтому их веса суммируются в ту же длительность. Это доказывает сохранение задачи, а не только показывает один совпавший числовой пример.
Общий старт и финиш включают все независимые части
Добавим источник s с нулевыми рёбрами во входы всех задач без предшественников. Выходы задач без последователей соединим нулевыми рёбрами с t. Тогда длиннейший s→t путь равен длительности критической цепочки всего проекта, включая независимые компоненты. Подключение только одной удобной начальной задачи могло бы пропустить более длинную ветвь.
Если исходный граф ацикличен, разделённый тоже ацикличен: внутреннее ребро проходит через одну задачу, а межзадачные стрелки сохраняют старый порядок. Нулевая длительность допустима и не создаёт цикл. Но исходные циклические зависимости не исчезают после разделения; преобразование сохраняет конфликт, а не решает его.
Срок проекта зависит от модели ресурсов
Критическая цепочка даёт срок при неограниченном параллелизме и запуске каждой задачи после всех предпосылок. Если один исполнитель должен выполнять все задачи по очереди, ресурсное ограничение не закодировано простыми стрелками исходной модели. Тогда ответ длиннейшего пути может быть меньше реального необходимого времени.
Не следует заменять каждое исходящее ребро весом самой вершины без анализа начала и конца. Такой приём способен потерять последнюю задачу или начислить начальную не тем способом. Вход-выход модель делает каждое начисление явным и облегчает проверку границ. Она также подходит для дополнительных ограничений пропускной способности вершин, но это уже другая постановка.
Четыре работы с двумя концами
Условие. Длительности A=4,B=3,C=2,D=5; зависимости A→C,B→C,A→D. Найдите срок проекта через разделение вершин при неограниченных ресурсах.
- Создаём четыре внутренних ребра весов 4,3,2,5. Каждая исходная зависимость становится нулевым ребром между выходом и следующим входом.
- Источник соединён с A_in,B_in; к цели идут C_out,D_out. Все добавленные внешние рёбра имеют вес 0.
- Три цепочки задач имеют длительности A,C:6; B,C:5; A,D:9. Поэтому длиннейший преобразованный путь имеет вес 9.
- Ранний запуск подтверждает срок: A заканчивается в 4,B в 3,C в 6,D в 9. Последняя завершённая работа D задаёт итог проекта.
Ответ. Минимальный срок в заданной параллельной модели равен 9, критическая цепочка A,D.
Проверка. Любое расписание должно потратить 4+5=9 на обязательную цепочку A→D. Показанное раннее расписание достигает этой нижней границы, поэтому срок доказан с двух сторон.
Где легко ошибиться. Нулевые рёбра зависимости не должны начислять длительность ещё раз. Каждая работа учитывается только на собственном внутреннем переходе, включая последнюю работу цепочки.
Проверьте понимание
Вопросы к этой главе
Что происходит с изолированной задачей?
Она получает собственное внутреннее ребро и подключается к общим s,t. Поэтому её длительность участвует в максимуме проекта и не теряется из-за отсутствия зависимостей.
Можно так решить расписание одного исполнителя?
Само преобразование сохраняет зависимости и длительности, но не добавляет ограничение общей занятости исполнителя. Для этой иной задачи нужны ресурсные условия сверх обычного DAG.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James Aspnes, Yale: TopologicalSort
Авторские университетские заметки: вебом проверены определение порядка DAG и линейная стоимость обычной сортировки. Критерий единственности и обновления при добавлении ребра доказаны в данной главе отдельно.
Макс-плюс алгебра расписаний и маршрутов
Максимальный вес маршрута заданного числа шагов удобно вычислять матричной степенью, если сложение вариантов заменить максимумом, а последовательное соединение — обычной суммой. Так возникает макс-плюс алгебра.
Перед началом: Матричное произведение; Максимум и сумма.
Две операции имеют другие нейтральные элементы
На ℝ∪{−∞} определим a⊕b=max(a,b), a⊗b=a+b с соглашением−∞+a=−∞. Нейтральный элемент для⊕равен−∞, а для⊗равен 0. Поэтому число 0 не играет роль отсутствия связи: оно означает допустимый переход нулевого веса. Отсутствующий переход нужно обозначать именно−∞.
Матричное произведение задаётся(A⊗B)ᵢⱼ=maxₖ(Aᵢₖ+Bₖⱼ). При соглашении строка=источник, столбец=цель оно соединяет первый фрагмент маршрута со вторым через k. Операция ассоциативна благодаря ассоциативности суммы и распределению суммы по максимуму, что разрешает обычное двоичное возведение в степень с новыми операциями.
Степень фиксирует число переходов
Элемент A^(⊗k)ᵢⱼ равен максимальному суммарному весу маршрута длины ровно k из i в j. Для нулевого числа шагов единичная матрица имеет 0 надиагонали и−∞ вне её: пустой маршрут существует только из вершины в себя. Обычная матрица с единицами на диагонали здесь не является единичной.
Для длины не больше K нужны I⊕A⊕…⊕A^(⊗K). Одна степень не разрешает произвольно остановиться раньше. Это различие особенно заметно при отрицательных весах и отсутствии петель. При заданном конечном k циклы допустимы: маршрут может повторять вершины, а число шагов всё равно ограничено.
Неограниченный горизонт требует отдельного анализа
Положительный доступный цикл позволяет неограниченно увеличивать вес при повторении, поэтому задача о максимуме по всем длинам может не иметь конечного ответа. Это не мешает каждой фиксированной степени быть корректно определённой. Для DAG достаточно конечных длин, поскольку вершины не повторяются, но макс-плюс степени полезны и в циклических моделях с фиксированным горизонтом.
Проверять небольшой результат лучше прямым перечислением промежуточных вершин. Так видно, какие невозможные фрагменты должны дать−∞, а какие допустимые нулевые переходы сохраняют вес. Использование большой конечной отрицательной заглушки вместо−∞ может породить ложный маршрут после сложения с большим положительным весом.
Два шага вместо произвольной длины
Условие. Вершины A,B, рёбра A→B:2,B→A:3,B→B:1. Постройте макс-плюс матрицу и её квадрат в соглашении строка=источник.
- Исходная матрица M=[[-∞,2],[3,1]]. Отсутствующее A→A не заменяется нулевым ребром.
- Из A в A за два шага доступен только A,B,A веса 5. Из A в B только A,B,B веса 3.
- Из B в A только B,B,A веса 4. Из B в B варианты B,A,B веса 5 и B,B,B веса 2, поэтому выбирается 5.
- Получаем M^(⊗2)=[[5,3],[4,5]]. Все клетки относятся ровно к двум переходам, даже когда одношаговый вариант имел бы другой вес.
Ответ. M^(⊗2)=[[5,3],[4,5]].
Проверка. Перечисление двух возможных промежуточных вершин в каждой клетке даёт те же четыре максимума. Умножение на матрицу diag(0,0) с−∞ внедиагонали сохраняет M.
Где легко ошибиться. В макс-плюс алгебре ноль является допустимым весом и мультипликативной единицей. Отсутствие перехода обозначается−∞, а единичная матрица отличается от обычной числовой.
Проверьте понимание
Вопросы к этой главе
Можно применять быстрое возведение в степень?
Да, ассоциативность нового матричного произведения сохраняется. Но все сложения и умножения внутри алгоритма должны использовать именно макс-плюс правила, включая обработку−∞.
Почему положительный цикл не портит квадрат матрицы?
Квадрат разрешает только два шага. Неограниченное повторение цикла запрещено фиксированным горизонтом и становится проблемой лишь в задаче по всем возможным длинам.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Zdeněk Hurák: Max-plus algebra
Первичные авторские материалы курса HybridSystems: вебом прочитаны max-plus операции, нейтральные элементы, матричные степени и связь с ориентированным графом. В главе отдельно задано соглашение строка=источник; пример не взят из источника.
Параметрический длиннейший путь и верхняя огибающая прямых
Если веса дуг зависят от параметра аффинно, стоимость каждого пути является прямой. Длиннейший путь в DAG выбирает верхнюю огибающую этих прямых. Не каждое попарное пересечение становится точкой переключения: его может скрывать третий маршрут с большей стоимостью.
Перед началом: Длиннейший путь в ациклическом графе; Аффинная функция и пересечение прямых.
Максимум аффинных стоимостей имеет конечные участки
Пусть вес дуги e равен a_eλ+b_e. Для фиксированного пути P сумма имеет вид A_Pλ+B_P. В конечном DAG путей конечное число, поэтому оптимальная стоимость из старта в достижимую вершину является максимумом конечного семейства аффинных функций. Это выпуклая непрерывная кусочно-линейная функция параметра.
На открытом участке без переключения оптимален один маршрут либо несколько маршрутов с совпадающей прямой. В точках равенства могут сосуществовать разные оптимальные пути. Недостижимую вершину по-прежнему обозначают отдельным состоянием минус бесконечность; её нельзя включать в обычную огибающую как нулевую стоимость.
Топологическая динамика переносится на функции
Вместо одного числа храним для вершины верхнюю огибающую стоимостей путей. Переход по дуге прибавляет её аффинную функцию ко всем участкам предшественника, а объединение входящих вариантов берёт максимум. Топологический порядок сохраняет отсутствие циклических зависимостей даже при отрицательных весах отдельных дуг.
Количество участков может расти, поэтому один проход по вершинам не означает ту же численную стоимость, что при одном фиксированном λ. В малом примере все пути можно перечислить и построить огибающую прямо. В более крупной реализации нужны точные пересечения и удаление неактивных участков; поточечный выбор маршрута при одном λ не заменяет эту задачу.
Пересечение двух проигрывающих путей не является событием
Для каждой пары прямых можно решить равенство, но затем нужно проверить доминирование над всеми остальными вариантами по обе стороны. Если третий путь выше в точке и её окрестности, пересечение не меняет оптимальный маршрут. Это особенно важно при интерпретации чувствительности модели.
При рациональных коэффициентах точки переключения можно хранить точными дробями. На границе полезно возвращать полный набор оптимальных маршрутов, а для численного запроса — согласованное правило выбора одного из них. Отрицательные веса в DAG не создают бесконечного ответа: повторять цикл здесь невозможно, поэтому верхняя огибающая остаётся конечной для каждого конечного λ.
Средний маршрут скрывает пересечение крайних
Условие. В DAG имеются только пути s→u→t, s→v→t, s→w→t с весами дуг соответственно (λ,4), (8−λ,0), (0,7). Постройте оптимальную стоимость на всей вещественной оси и найдите ответ при λ=2.
- Три стоимости равны P=λ+4, Q=8−λ и R=7. Попарные пересечения P=R и Q=R находятся при λ=3 и λ=1.
- При λ<1 имеем Q>7 и Q>P, поэтому оптимален путь через v. При 1<λ<3 обе наклонные прямые ниже семи, оптимален путь через w.
- При λ>3 имеем P>7 и P>Q, поэтому оптимален путь через u. На границах один и три возникают соответствующие пары оптимальных маршрутов.
- Прямые P и Q пересекаются при λ=2 со значением шесть. Но R=7 выше обеих, поэтому в этой точке нет переключения оптимума.
- При λ=2 длиннейший путь проходит через w и имеет стоимость семь. Формула огибающей: 8−λ при λ≤1, 7 при 1≤λ≤3, λ+4 при λ≥3.
Ответ. Точки переключения равны 1 и 3; при λ=2 оптимум 7 и маршрут s→w→t. Пересечение двух других прямых при 2 неактивно.
Проверка. Прямая подстановка на каждом из трёх интервалов проверяет все сравнения. Независимые неравенства Q≥R при λ≤1 и P≥R при λ≥3 доказывают формулу на неограниченных хвостах.
Где легко ошибиться. Не объявляйте каждое пересечение стоимостей двух путей точкой смены оптимального решения. Оно должно лежать на верхней огибающей, а не под ней.
Проверьте понимание
Вопросы к этой главе
Почему огибающая выпуклая, хотя обычный кратчайший путь даёт другую форму?
Здесь максимизируются аффинные функции, а их максимум выпуклый. Для кратчайшего пути берётся минимум, дающий вогнутую огибающую; направление оптимизации нельзя менять незаметно.
Что возвращать ровно при λ=1?
Максимальная стоимость семь достигается путями через v и w. Если интерфейс требует один маршрут, нужен отдельный согласованный выбор, но математически оптимальны оба.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Young, Tarjan, Orlin: parametric path problems
Прочитана постановка параметрических путей в начале §2. Источник изучает кратчайшие пути со специальными параметризованными дугами; здесь отдельно задан общий аффинный DAG и доказана верхняя огибающая для максимизации. Алгоритм и сложность статьи не присваиваются этому учебному построению.
Перенос корня за линейное время даёт все суммы расстояний дерева
Поиск из одной вершины легко даёт сумму расстояний до остальных. Повторение поиска для каждого возможного корня требует квадратичного времени. В дереве переход через ребро изменяет каждое расстояние ровно на единицу с известным знаком. Размер отрезанного поддерева поэтому позволяет получить соседний ответ за постоянное время и вычислить все суммы двумя проходами.
Перед началом: Единственный простой путь между вершинами дерева; Размер поддерева и обход в обратном порядке.
Первый корень нужен только для организации вычислений
Конечное связное неориентированное дерево, каждое ребро имеет длину 1; расстояния суммируются до всех вершин.
Выберем произвольный корень r. Снизу вверх вычислим size(v) — число вершин в поддереве v, включая саму v. Одновременно можно вычислить down(v), сумму расстояний от v до вершин этого поддерева. Для ребёнка c его вклад равен down(c)+size(c): каждое расстояние из c увеличивается на одно ребро.
Базы листа равны size=1 и down=0. После объединения всех детей down(r) уже является полным ответом D(r). Ориентация от корня служит для расчёта, но не меняет исходное неориентированное дерево и не означает запрет ходить в обратную сторону.
Разрез ребра определяет знак каждого изменения
Рассмотрим ребро родитель p — ребёнок c. После удаления ребра сторона c содержит size(c) вершин. При переносе точки отсчёта из p в c до каждой из них становимся на единицу ближе; до остальных n−size(c) — на единицу дальше. Поэтому D(c)=D(p)−size(c)+(n−size(c))=D(p)+n−2size(c).
Единственность пути в дереве является решающим условием: путь к любой вершине однозначно определяет, через какую сторону ребра он идёт. В графе с циклом после переноса может измениться выбранный кратчайший путь, и одного размера поддерева произвольного остовного дерева уже недостаточно.
Второй проход распространяет полные ответы
Идём сверху вниз от r, применяя формулу к каждому ребёнку после вычисления ответа родителя. Размеры поддеревьев при этом остаются относительно первоначального корня: не нужно физически перестраивать дерево на каждом шаге. Каждый из двух проходов рассматривает каждое ребро постоянно много раз, поэтому суммарное время O(n), память O(n).
Для контроля можно сложить все D(v). Каждая неупорядоченная пара вершин учитывается дважды. Независимая формула суммы расстояний по парам равна сумме size(c)(n−size(c)) по рёбрам: ребро входит в путь ровно тех пар, которые оно разделяет. Совпадение этих двух сумм проверяет ответы и размеры разрезов одновременно.
Центральная вершина выигрывает без перебора корней
Условие. Дерево на вершинах 0,…,7 имеет рёбра 0—1,1—2,1—3,3—4,3—5,5—6,5—7. Найдите суммы расстояний из всех вершин, выбрав первоначальным корнем 0.
- Снизу вверх размеры поддеревьев в порядке 0,…,7 равны [8,7,1,5,1,3,1,1]. Глубины относительно 0 равны [0,1,2,2,3,3,4,4], поэтому D(0)=19.
- Через ребро 0—1 получаем D(1)=19+8−14=13. Для его ребёнка 2: D(2)=13+8−2=19; для ребёнка 3: D(3)=13+8−10=11.
- Из 3 переносим ответ к 4 и 5: D(4)=11+8−2=17, D(5)=11+8−6=13. Затем D(6)=D(7)=13+8−2=19.
- Полный массив равен [19,13,19,11,17,13,19,19]. Минимум 11 достигается в вершине 3. Полусумма массива равна 65; вклады рёбер 7,7,15,7,15,7,7 также дают 65.
Ответ. Суммы расстояний: 19,13,19,11,17,13,19,19. Минимизирующая вершина — 3.
Проверка. Восемь независимых BFS по исходному дереву дают тот же массив. Дополнительно формула разрезов подтверждает общую сумму расстояний по всем 28 неупорядоченным парам, равную 65.
Где легко ошибиться. Не пересчитывайте size(c) относительно каждого нового корня внутри второго прохода. Формула переноса использует фиксированную сторону исходного разреза ребра.
Проверьте понимание
Вопросы к этой главе
Что изменится для положительных длин рёбер?
При длине w изменение станет w(n−2size(c)), а первый проход тоже должен учитывать w. Число вершин по обе стороны остаётся тем же; в этой главе worked использует только единичные длины.
Почему расстояние до самой вершины не требует отдельной поправки?
Оно включено в разбиение всех n вершин. При переходе p→c расстояние до c уменьшается с 1 до 0, а до p увеличивается с 0 до 1, как и требует общая формула.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- CSES — Tree Distances II
Официальная постановка задачи о суммах расстояний из всех вершин дерева. Формула переноса, доказательство разрезом и восьмивершинный пример выведены независимо.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Число путей в DAG: складываем способы, а не длины
Количество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.
Открыть темуСильные компоненты: какие вершины взаимно достижимы
Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.
Открыть тему