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

А если не только длина

А если спросят сам путь

«Сколько рёбер в кратчайшем пути», «через какую вершину он приходит в сотню», «выпишите путь» - всё это Форд–Беллман плюс одна строчка памяти.

Запоминаем, откуда пришли

Тут придётся отказаться от min: он молча возвращает меньшее и не говорит, сработало улучшение или нет. Пишем явное сравнение и внутри него запоминаем ребро.

prev[j] = i пишется внутри if, а не рядом с ним. Иначе в памяти осядет последнее ребро файла, а не лучшее.

Как разворачивается путь

Встаём в вершину 100 и шагаем назад: prev[100], потом prev от неё, и так до единицы. Получается путь задом наперёд — разворачиваем.

Рёбра и вершины — разные числа

В пути из четырёх вершин три ребра. Спрашивают количество рёбер — вычитай единицу.

Когда кратчайших путей несколько

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

Пример

Как разворачивается путь

Программа помнит по одной вершине на каждый рекорд. Возьмём готовую память нашего графа и пройдём по ней руками.

prev = [0] * 1001
prev[66] = 1                                 # так выглядит память после счёта
prev[670] = 66
prev[100] = 670

path = [100]                                 # встаём в финиш
while path[-1] != 1:
    path.append(prev[path[-1]])              # шагаем назад
    print(path)

path.reverse()
print(path)
print(len(path) - 1)                         # рёбер на единицу меньше

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

[100, 670]
[100, 670, 66]
[100, 670, 66, 1]
[1, 66, 670, 100]
3

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

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

строка	что делает
`prev = [0] * 1001`	откуда пришли в каждую вершину
`if dist[i] + w < dist[j]`	явное сравнение вместо min, чтобы поймать момент улучшения
`prev[j] = i`	пишется внутри if, иначе осядет случайное ребро
`path[-1]`	последняя вершина списка
`while path[-1] != 1`	шагаем назад, пока не придём в старт
`len(path) - 1`	число рёбер, а не вершин

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

INF = float('inf')
dist = [INF] * 1001
dist[1] = 0
prev = [0] * 1001                            # prev[j] - откуда пришли в j

for step in range(1000):
    for i, j, w in data:
        if dist[i] + w < dist[j]:            # явное сравнение вместо min
            dist[j] = dist[i] + w
            prev[j] = i                      # запомнили сработавшее ребро

path = [100]
while path[-1] != 1:
    path.append(prev[path[-1]])

path.reverse()
print(path)
print(len(path) - 1)                         # рёбер на единицу меньше
print(path[-2])                              # предпоследняя вершина

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

[1, 66, 670, 100]
3
670

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

Кратчайший — не значит с наименьшим числом рёбер.

Ловушки

Посчитали вершины вместо рёбер.
Забыли развернуть путь и назвали первой вершину 100.
Оставили min и не поняли, куда вписать prev.
Записали prev[j] при каждом просмотре ребра, а не только при улучшении.
Пошли назад по prev, когда до сотни пути нет. Цикл не кончится, prev там нулевой.

Проверь себя

Файл graph.txt: отметьте вершины, через которые проходит кратчайший путь из вершины 1 в вершину 31.

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

Файл graph.txt: сколько рёбер в кратчайшем пути из вершины 1 в вершину 31?

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

Attached files
graph.txt

Печать