Задание 23. Графы: кратчайший путь и число путей

Задание 23 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле (граф этого примера нарисован ниже, в разборе):

100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5

Для приведённого примера верным ответом будет 7.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл с данными: demo_23.txt. Положите его рядом со скриптом, не переименовывая: программа в разборе открывает demo_23.txt.

Сначала – пример руками. Он маленький, и на нём видно, что вообще просят. Из вершины 1 выходят три ребра, и за каждым своя дорога до 100:

• напрямую 1 → 100: 12;
• через 7: 5.5 + 2 = 7.5;
• через 4: 2.5 + 8 = 10.5.

Кратчайший путь – 7.5, целая часть – 7, как и обещает условие.

Перебрать все пути не выйдет. В примере их три, а в файле демоверсии путей из 1 в 100 – 2 033 652 335. Выписать каждый и сложить веса программа не успеет.

Идти по самому лёгкому ребру тоже нельзя. Из 1 самое лёгкое ребро ведёт в 4 (вес 2.5), но путь через 4 стоит 10.5, а через 7 – 7.5. Дешёвое начало ничего не обещает про продолжение.

Идея: хранить не пути, а одно число на вершину. Заведём таблицу best: для каждой вершины – длину кратчайшего пути до неё из 1, которую мы уже знаем. Для самой вершины 1 это 0. Если до вершины $a$ путь длиной $\text{best}(a)$ уже найден, а из $a$ в $b$ ведёт ребро веса $w$, то в $b$ можно прийти за $\text{best}(a) + w$. Из всех рёбер, входящих в $b$, берём самое выгодное:

$$\text{best}(b) = \min_{a \to b} \left( \text{best}(a) + w_{ab} \right)$$

Ответ для вершины собирается из готовых ответов для вершин перед ней – это и есть динамическое программирование.

Остаётся вопрос порядка. Число для $b$ можно посчитать, только когда готовы числа всех вершин, из которых в $b$ ведут стрелки. А рёбра в файле перемешаны: в примере ребро 7 → 100 записано раньше, чем 1 → 7, так что за один проход по файлу до 100 через 7 не добраться.

Поэтому таблицу считают проходами. Каждый проход идёт по всем рёбрам и строит новую таблицу по старой. После первого прохода известны пути из одного ребра, после второго – из не более чем двух, и так далее. Когда проход ничего не изменил, считать дальше незачем: следующий дал бы то же самое. Граф без циклов, поэтому путей бесконечной длины в нём нет, и проходы когда-нибудь закончатся – на файле демоверсии их 13.

Ниже – все проходы на примере из условия. Число у вершины – её значение в best; ребро из вершины без числа пропускается. Обратите внимание на второй проход: у 100 было 12, а стало 7.5, потому что к этому моменту стало известно число у 7. Третий проход нужен уже только вершине 12, а четвёртый ничего не меняет – на нём программа и останавливается.

Программа пишется в три шага, и после каждого её стоит запустить на примере из условия: восемь строк примера сохраните в файл рядом со скриптом. Ошибку проще найти в маленьком файле.

Шаг 1. Прочитать рёбра. Каждое ребро – тройка «откуда, куда, вес», складываем их в список:

edges = []                          # рёбра: (откуда, куда, вес)
with open('demo_23.txt') as f:
    for line in f:
        parts = line.split()        # разделители - любые пробелы и табуляции
        if parts:                   # чтоб не добавлялась пустая строка в конце файла
            edges.append((int(parts[0]), int(parts[1]), float(parts[2])))
print(len(edges))

На примере должно напечататься 8. Номера вершин – int, а вес – float.

Шаг 2. Один проход. Таблица best – словарь: ключ – номер вершины, значение – длина пути до неё. В новую таблицу new сразу кладём старт. Потом идём по рёбрам и для каждого ребра $a \to b$ проверяем, известен ли путь до $a$. Если да – предлагаем для $b$ длину best[a] + w и оставляем меньшее из того, что там уже есть. new.get(b, float('inf')) значит «если для $b$ ещё ничего не записано, считай, что там бесконечность», – тогда первое же предложение и запишется:

best = {1: 0}                       # вершина -> длина кратчайшего пути из 1
new = {1: 0}                        # таблица после прохода
for a, b, w in edges:
    if a in best:                   # путь до a уже известен
        new[b] = min(new.get(b, float('inf')), best[a] + w)
print(new)

На примере: {1: 0, 7: 5.5, 100: 12.0, 4: 2.5}. Это пути из одного ребра – до 100 пока известна только дорога напрямую за 12.

Шаг 3. Повторять, пока таблица меняется. Оборачиваем проход в while True: после прохода сравниваем новую таблицу со старой, совпали – выходим, нет – новая становится старой, и всё сначала. Словари сравниваются целиком, == проверяет и ключи, и значения.

best = {1: 0}                       # вершина -> длина кратчайшего пути из 1
while True:
    new = {1: 0}                    # таблица следующего прохода
    for a, b, w in edges:
        if a in best:               # путь до a уже известен
            new[b] = min(new.get(b, float('inf')), best[a] + w)
    if new == best:                 # проход ничего не изменил – всё посчитано
        break
    best = new

Ответ. В best[100] лежит длина кратчайшего пути, а просят целую часть – int. На примере программа должна напечатать 7; напечатала – запускайте на файле задания.

Чего программа не знает. Она находит длину кратчайшего пути, но не сам путь: в таблице у каждой вершины лежит одно число, а через какие вершины оно получено, нигде не записано. Спросить её «каким путём идти из 1 в 100» нельзя – ответ уже потерян. В задании 23 это и не нужно: просят только длину.

Последние две строки – единственное место, где считают не до неизменной таблицы: после j проходов с пустой new в таблице лежат ровно пути из j рёбер, и остановиться надо именно там.

1. Один проход вместо нескольких. На примере один проход даёт у 100 число 12 – дорогу напрямую, – а верный ответ 7. Останавливаться можно только тогда, когда проход ничего не изменил, а не когда у цели появилось первое число.
2. Жадный выбор ребра. Идти каждый раз по самому лёгкому ребру: на примере это 10.5 вместо 7.5, на файле демоверсии – 45069 вместо 10971.
3. round вместо int. Просят целую часть: round(7.5) – это 8, а верный ответ 7. int отбрасывает дробную часть, round округляет.
4. split(' ') вместо split(). В файле числа разделены несколькими пробелами и табуляциями: вторая строка файла демоверсии – 73, восемь пробелов, 100, табуляция, 7990.0.
5. Ответили не на тот вопрос. Могут спросить длину пути, число рёбер в нём или число путей, и из какой вершины в какую: 1 → 100 и тд. Внимательно перечитайте последнюю строку условия и ответьте на задаваемый вопрос.