Кратчайший путь в графе

Что просят сделать

Это новое задание, и по смыслу оно похоже на навигатор в телефоне. Есть пункты, между ними дороги разной длины, и нужно найти самый короткий маршрут из одного пункта в другой.

На картинке с пятью пунктами ответ видно глазами. Но в задании дан файл, где пунктов и дорог тысячи, поэтому решаем кодом.

Как выглядит файл

В каждой строке одна дорога: откуда, куда и какой она длины.

1	20	10.0
1	5	4.5
5	20	3.0
20	8	1.5

Дороги односторонние, а циклов в графе нет: из 1 в 20 можно, а обратно только если в файле есть отдельная такая строка. Длина бывает дробной.

Простыми словами

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

На дорогу из пунктов A в B смотрим так: лучший путь до A плюс длина этой дороги. Если это короче того, что записано у B, записываем новое число.

Идея: уточняем снова и снова

Возьмём маленький граф и будем идти по строкам файла по порядку:

Старт в пункте 1. До него расстояние 0, до остальных пока неизвестно, запишем ∞. Вот что получается после каждого прохода по всему файлу:

Посмотри на первую строку файла, дорогу 5 → 20. В первом проходе она бесполезна: расстояние до 5 ещё неизвестно, а ∞ + 3 это снова ∞. Строки в файле идут в случайном порядке, поэтому одного прохода не хватает.

Выход простой: проходим по файлу ещё раз. Теперь расстояние до 5 уже известно, и эта же строка даёт путь до 20 короче прежнего. Так числа постепенно уточняются.

Когда остановиться? Когда очередной проход не изменил ни одного числа. Значит, все кратчайшие пути уже найдены. В таблице это последний проход: он совпал с предыдущим.

Шаг 1. Читаем файл

Сначала превращаем файл в список дорог. Учебный файл 23-demo.txt лежит рядом с кодом: 60 пунктов, номера от 1 до 60.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])

print(len(data))
print(data[0])

• line.split() разрезает строку на три части по пробелам и табуляциям.
• Номера пунктов целые, поэтому int. Длина может быть дробной, поэтому float.
• Каждая дорога лежит в data отдельным списком [a, b, l].

Шаг 2. Список расстояний

Нам нужно хранить лучшее расстояние до каждого пункта. Удобный приём: номер элемента списка это номер пункта. Тогда dist[7] это лучшее известное расстояние до пункта 7.

dist = [float('inf')] * 61
dist[1] = 0

Разберём по частям:

• float('inf') это бесконечность. Она больше любого числа, поэтому первая же найденная дорога окажется лучше.
• [x] * 61 создаёт список из 61 одинакового элемента. Посмотри сам: [1] * 3 даёт [1, 1, 1].
• Почему 61, а не 60? Индексы начинаются с нуля, а пункта с номером 0 нет. Чтобы существовал dist[60], нужен 61 элемент. Размер бери из условия: наибольший номер пункта плюс один.
• dist[1] = 0: от старта до самого себя идти ноль. Здесь старт это пункт 1, в задаче номер будет свой. Без этой строки все числа так и останутся бесконечностью.

Шаг 3. Ищем кратчайшие пути

Весь шаблон целиком. Он один на все задачи номера, дальше меняются только детали.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])

dist = [float('inf')] * 61
dist[1] = 0

while True:
    old = dist.copy()
    for a, b, l in data:
        dist[b] = min(dist[b], dist[a] + l)
    if old == dist:
        break

print(dist[60])

Главная строка:

dist[b] = min(dist[b], dist[a] + l)

Читается так: лучший путь до b это меньшее из двух чисел. Первое мы уже знаем, dist[b]. Второе получится, если прийти в a лучшим путём и пройти по этой дороге, dist[a] + l. Обрати внимание: прибавлять только l нельзя, ведь нужно расстояние от старта, а не от a.

Остальное:

• while True повторяет проходы, пока мы сами не остановим цикл.
• old = dist.copy() делает снимок списка перед проходом.
• if old == dist: break: если после прохода ничего не поменялось, все пути найдены.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
# дальше твой код

Обязательное первое и последнее ребро

Иногда условие требует: путь обязан начинаться с определённой дороги или заканчиваться определённой дорогой.

Самый простой способ: выбросить все дороги, по которым идти нельзя. Тогда алгоритм просто не сможет ошибиться.

Пусть путь из 1 в 60, первая дорога обязана вести в 14, а последняя обязана идти из 59. Какие строки файла лишние?

• из старта, но не в 14;
• в финиш, но не из 59.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a == 1 and b != 14:      # первое ребро обязано вести в 14
        continue
    if b == 60 and a != 59:     # последнее ребро обязано идти из 59
        continue
    data.append([a, b, l])

dist = [float('inf')] * 61
dist[1] = 0

while True:
    old = dist.copy()
    for a, b, l in data:
        dist[b] = min(dist[b], dist[a] + l)
    if old == dist:
        break

print(dist[60])

continue пропускает остаток шага цикла. До строки append мы не доходим, поэтому лишняя дорога в список не попадает. Вся остальная часть шаблона не меняется.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
# дальше твой код

Самый длинный путь и тупики

Встречается вопрос про самую длинную дорогу. Логика та же, только всё наоборот:

Минус бесконечность меньше любого числа, поэтому первая найденная дорога окажется лучше неё.

Что такое тупик

Тупик это пункт, из которого не выходит ни одна дорога. Значит, его номер ни разу не стоит на месте a. Собираем все номера, которые встречались как a, а остальные и есть тупики:

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])

dist = [-float('inf')] * 61
dist[5] = 0

while True:
    old = dist.copy()
    for a, b, l in data:
        dist[b] = max(dist[b], dist[a] + l)
    if old == dist:
        break

starts = {a for a, b, l in data}
tupiki = [x for x in range(1, 61) if x not in starts]
print(tupiki)
print(max(dist[x] for x in tupiki))

Фигурные скобки {a for ...} создают множество: номера без повторов, и проверка not in работает мгновенно. Недостижимые тупики сами отсеются: у них осталась минус бесконечность, и max их не выберет.

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
# дальше твой код

Второй способ: рекурсия как в №13

Эту же задачу можно решить иначе, и многие решают именно так. Способ похож на №13: там считали, сколько программ из одного числа в другое. Здесь граф без циклов, поэтому работает та же рекурсия, только вместо количества ищем наименьшую длину.

Выбери один способ и решай им все задачи. Способ с проходами короче для простых вопросов, а рекурсия удобнее для разновидностей из следующего раздела.

Простыми словами

Встань в пункт и спроси: куда я могу пойти отсюда? Длина лучшего пути от тебя равна длине дороги плюс лучшему пути из следующего пункта. Из всех дорог выбираем самую выгодную. Дошли до цели, осталось идти ноль. Попали в тупик, такой путь считаем бесконечным, и min его отбросит.

Сначала словарь

Для рекурсии удобно хранить для каждого пункта список дорог из него. Для этого подходит словарь:

d = { 1: [(20, 10.0), (5, 4.5), (3, 2.0)],
      5: [(20, 3.0)] }

Из пункта 1 идут три дороги: в 20 длиной 10, в 5 длиной 4,5 и в 3 длиной 2.

Весь код

from functools import cache

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))

@cache
def f(c, e):
    if c == e:                 # пришли в цель
        return 0
    if c not in d:             # тупик, сюда идти незачем
        return float('inf')
    return min(l + f(b, e) for b, l in d[c])

print(f(1, 60))

• c not in d значит, что из этого пункта нет дорог.
• l + f(b, e) это длина дороги плюс лучший путь от следующего пункта.
• @cache запоминает уже посчитанные пункты. На маленьком файле код работает и без него, но на большом без кэша он почти не закончится: путей слишком много.

Для самого длинного пути всего две замены: max вместо min и -float('inf') вместо float('inf').

Разновидности задачи

Вот какие ещё бывают вопросы. Каждый решается маленькой правкой функции из прошлого раздела.

Не проходит через вершину

Запрещённый пункт считаем таким же плохим, как тупик. Здесь нельзя идти через пункт 30:

if c not in d or c == 30:
    return float('inf')

Проходит через вершину

Путь разбивается на две части, а длины складываются. В №13 в этом месте было умножение, потому что считали количество. Здесь длины, поэтому плюс:

print(f(1, 31) + f(31, 60))

Содержит конкретное ребро

Та же идея: путь до начала ребра, само ребро и путь от его конца.

print(f(1, 31) + 1.62 + f(45, 60))

Не больше k рёбер

Добавляем третий параметр: сколько рёбер ещё можно потратить. Кэш здесь работает, потому что ответ зависит только от пункта и остатка.

from functools import cache

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))

@cache
def f(c, e, k):
    if c == e:
        return 0
    if c not in d or k == 0:
        return float('inf')
    return min(l + f(b, e, k - 1) for b, l in d[c])

print(f(1, 60, 7))

Наименьшее число рёбер

Вместо длины дороги прибавляем единицу, и функция считает рёбра:

from functools import cache

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))

@cache
def f(c, e):
    if c == e:
        return 0
    if c not in d:
        return float('inf')
    return min(1 + f(b, e) for b, l in d[c])

print(f(1, 60))

Длина в заданных пределах

Например: самый длинный путь, но не больше 22. Тут нельзя запоминать один ответ на пункт, и это самая коварная разновидность. Лучший путь от промежуточного пункта может вылезти за предел, а чуть более короткий подошёл бы. Кэш же хранит только один лучший ответ на пункт, поэтому нужный вариант теряется. Приходится перебирать все пути и держать накопленную сумму параметром:

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))

def f(c, e, s):
    if c == e:
        return s if s <= 22 else -float('inf')
    if c not in d:
        return -float('inf')
    return max(f(b, e, s + l) for b, l in d[c])

print(f(40, 60, 0))

Это видно прямо на учебном файле: перебор находит 21,99, а если убрать параметр s и запоминать один лучший ответ на пункт, получится 19,46, то есть неверный ответ. На большом файле это может считаться очень долго, ведь перебираются все пути. Такие задачи на экзамене маловероятны, но в списке возможных разновидностей они есть.

Сводка

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))
# дальше твой код

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))
# дальше твой код

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))
# дальше твой код

d = {}
for line in open('23-demo.txt'):
    a, b, l = line.split()
    a, b, l = int(a), int(b), float(l)
    if a not in d:
        d[a] = []
    d[a].append((b, l))
# дальше твой код

Как записать ответ

Часто просят целую часть длины. Хочется написать int(dist[60]), но тут есть подвох. Дробные числа Python считает с крошечной погрешностью:

print(0.1 + 0.2)

Сумма может оказаться чуть меньше настоящей, например 284.99999999999994 вместо 285. А int просто отбрасывает дробную часть и даст 284.

Поэтому выведи число как есть и посмотри на него глазами. Если после запятой длинный ряд девяток, настоящее число это следующее целое.

Ловушки

Практика

Порядок действий одинаков для любой задачи номера:

1. Прочитай условие: откуда, куда, что особенного и какой наибольший номер пункта.
2. Выбери способ: проходы с dist или рекурсию.
3. Учти особенности: запреты, max вместо min, тупики, число рёбер.
4. Запусти, посмотри на число и запиши ответ.

Закрепи всё на учебном файле, без подсказок:

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
# дальше твой код

data = []
for line in open('23-demo.txt'):
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
# дальше твой код