Кратчайший путь во взвешенном графе
Направление и вес ребра, достижимость и принцип вычисления кратчайших расстояний через предшественников.
Граф задаёт объекты и разрешённые переходы между ними. Если каждому переходу приписана длина или стоимость, возникает задача найти путь с наименьшей суммой этих значений. Для ациклического ориентированного графа расстояние до очередной вершины можно выразить через расстояния до её предшественников. Это позволяет сравнивать пути, не выписывая каждый из них целиком.
Вершина, ребро и его вес
Вершина представляет объект, а ребро — связь между двумя объектами. В ориентированном графе у каждого ребра есть начало и конец. Запись u\to v разрешает переход из вершины u в вершину v; обратное движение требует отдельного ребра.
Вес — число, приписанное ребру. Граф с такими числами называется взвешенным. В задаче о длине пути вес показывает длину одного перехода. Номер вершины служит только её именем: разность номеров не определяет ни длину, ни направление ребра.
Например, строка 6 1 1.0 в примере с направленными переходами ↗ задаёт ребро 6\to1 веса 1. Из неё нельзя заключить, что из 1 достижима 6. Для такого вывода понадобился бы путь, все стрелки которого направлены от 1 к 6.
Длина пути и достижимость
Путь — последовательность рёбер, по которым можно пройти одно за другим в разрешённом направлении. Если он содержит k рёбер с весами w_1,\ldots,w_k, его длина равна w_1+\ldots+w_k. Количество рёбер и сумма их весов — разные характеристики.
В небольшом графе из того же задания прямой переход 1\to100 имеет вес 12. Переходы 1\to7 и 7\to100 имеют веса 5{,}5 и 2. Поэтому путь через 7 содержит больше рёбер, но имеет меньшую длину: 5{,}5+2=7{,}5<12.
Вершина достижима из старта, если до неё существует путь. Наличие вершины в файле ещё не означает её достижимость. Даже входящее в неё ребро не помогает, если до начала этого ребра добраться нельзя.
Лучшее расстояние до вершины
После выбора старта минимальная длина пути до вершины v обозначается d(v). Если старт — вершина 1, то d(1)=0: путь без переходов уже находится в начальной вершине и имеет нулевую длину.
Для недостижимой вершины используется d(v)=\infty. Бесконечность здесь является удобной отметкой отсутствия пути, а не длиной реального маршрута. Она сохраняет смысл сравнения: \infty+w=\infty для конечного веса, а минимум конечного расстояния и бесконечности равен конечному расстоянию. Ноль для недостижимой вершины не подходит: он означал бы бесплатный путь из старта.
Почему достаточно рассмотреть последнее ребро
Любой непустой путь до вершины v заканчивается некоторым ребром u\to v. До этого перехода путь должен добраться до u. Если эта часть длиннее, чем лучший путь до u, её можно заменить более короткой и сохранить то же последнее ребро. Получится меньшая общая длина.
Следовательно, для фиксированного последнего ребра достаточно лучшего расстояния до его начала. Если вес ребра обозначен w(u,v), длина кандидата равна d(u)+w(u,v). Кратчайший путь выбирается сравнением кандидатов для всех входящих рёбер:
d(v)=\min_{u\to v}\bigl(d(u)+w(u,v)\bigr) при v\ne1.
Такое равенство называется рекуррентным соотношением. Оно охватывает все пути, потому что у каждого пути обязательно есть последнее ребро. Если входящих рёбер нет, пути из другого старта тоже нет. Если все их начала недостижимы, все кандидаты равны бесконечности.
Небольшой фрагмент исходного примера показывает роль недостижимой вершины. В 7 входят рёбра из 1 веса 5{,}5 и из 6 веса 7. При d(1)=0 и d(6)=\infty получается d(7)=\min(0+5{,}5,\infty+7)=5{,}5. Второе ребро есть в графе, но не даёт пути от выбранного старта.
Ацикличность и порядок вычисления
Ориентированный цикл позволил бы, двигаясь по стрелкам, вернуться в исходную вершину после одного или нескольких переходов. В ациклическом графе таких возвратов нет. Поэтому зависимость расстояния от предшественников не может замкнуться сама на себя.
На этом основана рекурсивная запись: функция расстояния до одной вершины вызывает ту же функцию для начал входящих рёбер. Вычисление идёт назад по зависимостям, пока не встретит старт с расстоянием 0 либо вершину без входящих рёбер с расстоянием \infty. Затем найденные значения используются для вычислений, ожидающих их результата. Направления самих рёбер при этом не меняются: ищется длина пути от старта, а не обратного пути.
Номера вершин не определяют этот порядок. Например, переход 975\to625 из реального входного файла означает, что при вычислении расстояния до 625 может понадобиться расстояние до 975. Ацикличность запрещает замкнутые цепочки, но не запрещает переходы от большего номера к меньшему.
Зачем сохранять вычисленные значения
Разные ветви вычисления могут обратиться к одному предшественнику. Без сохранения результата функция повторно исследовала бы те же входящие рёбра. Кеширование запоминает пару «аргумент функции — результат»: после первого вычисления d(7) все следующие запросы этого расстояния получают готовое число.
В Python такую работу выполняет декоратор @cache из functools, записанный над определением функции. Список рёбер сначала читается полностью и после этого не меняется: тогда сохранённое расстояние остаётся верным. В сочетании с рекуррентным соотношением это даёт динамическое программирование.
Каждая нужная вершина вычисляется один раз, а каждое её входящее ребро создаёт один кандидат. Поэтому объём работы определяется числом вершин и рёбер, участвующих в вычислении, а не числом всех различных путей. Сам путь для нахождения его длины хранить не обязательно.
Десятичные веса и целая часть
Сравнение выполняется по полным суммам весов. Если условие требует целую часть минимальной длины, это отдельное действие после нахождения минимума. Для положительного результата оно совпадает с округлением вниз: у числа 7{,}5 целая часть равна 7, а не ближайшему целому 8.
Усечение каждого веса заранее меняет исходную задачу. Например, два перехода веса 1{,}6 дают сумму 3{,}2 с целой частью 3. Если сначала заменить оба веса на 1, получится 2. Этот небольшой пример показывает, почему дроби сохраняются до последнего действия.
Для десятичных записей из файла подходит тип Decimal, создаваемый непосредственно из строки веса. Он не вносит двоичное приближение, свойственное преобразованию строки в float. Точность десятичных вычислений тоже ограничена выбранным контекстом; стандартного контекста достаточно для чисел рассматриваемого файла. Последующее int отбрасывает дробную часть уже найденной положительной длины.
От правила к решению
Как из строк файла получить все кандидаты для последнего ребра и не включить путь из недостижимой вершины? Почему вычисление по зависимостям остаётся верным, когда номера и строки перемешаны? В статье «Задание №23. Кратчайший путь» эти вопросы разобраны на небольшом графе, а затем то же правило применено программой к полному входному файлу.