Статья Автор: Деникина Н.В., Деникин А.В.

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

Почему про длинный путь вообще можно спрашивать

В графе с циклом вопрос бессмысленный: покрутился лишний раз — и путь стал длиннее, ответа нет.

Слово «ациклический» в условии стоит не для красоты. Циклов нет, крутиться негде, путей конечное число — значит, самый длинный существует.

Три правки в одной программе

Форд–Беллман не знает слова «короче». Он знает «лучше». Скажем ему, что лучше — это больше.

Меняется ровно три вещи: бесконечность становится минус бесконечностью, min становится max, и всё.

min на max, inf на -inf — программа готова.

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

Флойд для максимума не годится

В таблице Флойда пути склеиваются через пересадку, и для максимума такая склейка ломается: самый длинный путь из i в k и самый длинный из k в j могут пройти по одной и той же вершине дважды, а это уже не путь.

Для длинного пути остаётся Форд–Беллман — и работает он только потому, что граф ациклический.

На нашем файле

Кратчайший путь из 1 в 100 мы уже знаем — 30.8. Посмотрим, каким длинным он может быть.

Почему нельзя просто заменить min на max

Если оставить старт от плюс бесконечности, максимум навсегда останется бесконечностью. Проверим.

INF = float('inf')
NEG = float('-inf')

print(max(INF, 0 + 5.5))                     # рекорд так и остался бесконечным
print(max(NEG, 0 + 5.5))                     # а с минус бесконечностью всё честно
print(NEG + 100.0)                           # прибавление её не меняет
print(max(NEG, NEG + 3.0))                   # недостижимая вершина остаётся в стороне

Что печатает демонстрация

inf
5.5
-inf
-inf

Значит, правок ровно три: INF становится -inf, min становится max, и стартовый ноль остаётся на месте. Всё остальное в программе не трогаем.

Что делает каждая строка основной программы

строка	что делает
`dist = [NEG] * 1001`	стартуем от минус бесконечности
`dist[1] = 0`	до стартовой вершины по-прежнему ноль
`max(dist[j], dist[i] + w)`	теперь лучшее — это большее
`int(dist[100] + 0.000001)`	целая часть считается так же

data = []
for s in open("graph.txt"):
    v1, v2, w = s.split()                    # split() режет по любым пробелам и табуляциям
    data.append((int(v1), int(v2), float(w)))

NEG = float('-inf')
dist = [NEG] * 1001                          # теперь стартуем от минус бесконечности
dist[1] = 0

for step in range(1000):
    for i, j, w in data:
        dist[j] = max(dist[j], dist[i] + w)  # и берём большее

print(dist[100])
print(int(dist[100] + 0.000001))

Что печатает программа

203.4
203

203.4 против 30.8 — разница почти в семь раз, хотя граф один и тот же и программа отличается тремя символами. Перепутать формулировку в условии дорого стоит.

Ловушки

Поменяли min на max, а бесконечность оставили положительной. Все рекорды так и останутся inf.
Взяли Флойда и получили правдоподобное, но неверное число.
Ищут самый длинный путь в графе с кольцом. Там ответа нет.
Решили, что самый длинный путь идёт по наибольшему числу рёбер. Не обязательно.

Проверь себя

Файл graph.txt: целая часть длины самого длинного пути из вершины 1 в вершину 502.

Проверить ответ

Файл graph.txt: целая часть длины самого длинного пути из вершины 1 в вершину 810.

Проверить ответ

Attached files
graph.txt

Печать