Лучший путь до цели

Почему бы не выписать все пути, как в учебном графе?

Путей бывает слишком много. В файле задачи темы всего 200 рёбер, а путей из 1 в 100 — почти 150 миллиардов. Каждая развилка умножает число путей: две стрелки на каждом из 30 шагов дают 2³⁰ — больше миллиарда путей. Перебрать их все не успеет ни человек, ни программа.

А если на каждом шаге брать самую дешёвую стрелку? Не сработает. Из 1 самая дешёвая стрелка — в 4, за 2.5. Но из 4 до 100 идти ещё 8.0, всего 10.5. А путь через 7 начинается дороже, с 5.5, и выходит 7.5.

Дешёвый первый шаг ничего не говорит о том, сколько стоит остаток пути. Нужен способ, который учитывает весь остаток, но не перебирает пути по одному.

Что нужно знать о вершине, чтобы решить, идти ли через неё?

Только одно: сколько стоит лучший путь от неё до цели. Как мы в неё пришли, для остатка пути неважно. В вершину 7 можно прийти из 1 или из 6. Но дальше из 7 одна и та же дорога: 7 → 100 за 2.0. Каким бы путём мы ни пришли в 7, лучший остаток стоит 2.

Обозначим это число f(v) — длина кратчайшего пути из вершины v до цели. Здесь f(7) = 2; запись читается «эф от семи». Если знать f для всех вершин, ответ задачи — f(1): длина лучшего пути из 1 в 100.

Как найти f(v), если для соседей f уже известно?

Перебрать стрелки из v: к весу каждой прибавить f вершины, куда она ведёт, и взять наименьшую сумму. В самой цели f = 0 — идти уже некуда. Любой путь из v начинается с какой-то стрелки, а лучший остаток после неё стоит f её конца. Остаётся выбрать лучшую стрелку.

Считаем от цели назад — так у соседей f всегда уже есть:

• f(100) = 0 — мы уже в цели;
• f(7) = 2.0 + f(100) = 2;
• f(4) = 8.0 + f(100) = 8;
• f(1) = min(5.5 + f(7); 12.0 + f(100); 2.5 + f(4)) = min(7.5; 12; 10.5) = 7.5.

f(1) = 7.5 — тот же ответ, что дал перебор, хотя ни один путь целиком мы не выписывали. Посмотри расчёт по шагам: под вершинами появляются значения f, выделена стрелка, которая дала минимум.

Правило работает для любой вершины, не только для нужной в ответе: f(6) = min(7.0 + 2; 1.0 + 7.5) = 8.5. А почему у вершины 12 стоит ∞ — в следующем разделе.

Заметь, как устроено правило: чтобы найти f вершины, нужны f её соседей. Функцию, которая для ответа вызывает саму себя, называют рекурсивной. Так мы и запишем f на Python в подтеме 3.

Чему равно f(12)? Из 12 не выходит ни одной стрелки.

До цели из 12 не дойти, поэтому f(12) = ∞ — бесконечность, хуже любого настоящего пути. Ноль ставить нельзя: ноль значит «уже пришли».

Посмотрим, к чему приводит ноль. Добавим в учебный граф стрелку 4 → 12 весом 0.5. Если считать f(12) = 0, то f(4) = min(8.0 + 0; 0.5 + 0) = 0.5, а f(1) = 2.5 + 0.5 = 3. Но путь за 3 — это 1 → 4 → 12: он кончается в тупике, а не в 100.

С бесконечностью всё складывается само: ∞ плюс любое число — снова ∞, а любое настоящее число меньше ∞. Поэтому стрелка в тупик никогда не даёт минимум. Бесконечность бывает и у вершины со стрелками — если все они ведут в тупики.

• Перебор путейпутей бывают миллиарды — не успеть
• Жадный выбордешёвый первый шаг не гарантирует лучший путь
• f(v)длина кратчайшего пути из v до цели
• f(цели)0
• Правилоf(v) = min(вес + f(конца)) по стрелкам из v
• Тупикf = ∞, а не 0
• Учебный примерf(1) = 7.5