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

Кратчайший путь в графе: через вершину и в обход

Если путь лежит через вершину X

Путь через X разрезается этой вершиной на два куска, и каждый выгодно делать кратчайшим отдельно.

В таблице Флойда оба куска уже посчитаны, так что ответ — это одна строка.

W[1][X] + W[X][100] и всё.

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

Если путь лежит в обход вершины X

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

Если X не лежала на кратчайшем пути, ответ не изменится. Это нормально и часто бывает.

Пример

Посчитаем: обычный кратчайший путь, путь через вершину 486 и путь в обход вершины 670.

Одна строка вместо второго алгоритма

Когда таблица Флойда готова, путь через вершину складывается из двух её клеток. Посмотрим на числа.

a = 31.1                                     # W[1][486] - от единицы до вершины 486
b = 9.8                                      # W[486][100] - от неё до сотни

print(a + b)                                 # путь через вершину 486

Результат работы программы

40.900000000000006

Ограничение не может помочь: путь через заданную вершину всегда не короче обычного. А если хоть одна из двух клеток бесконечна, такого пути просто не существует.

Разбор программы

строка	что делает
`W[1][486] + W[486][100]`	путь через вершину — две клетки таблицы
`if v1 != 670 and v2 != 670`	ребро не заносится, если касается запрещённой вершины
`B = [[INF] * 1001 ...]`	для запрета строим вторую таблицу с нуля
`for k in vertices`	вторую таблицу тоже надо прогнать через Флойда

INF = float('inf')
W = [[INF] * 1001 for _ in range(1001)]      # W[i][j] - кратчайший путь из i в j
vertices = set()

for s in open("graph.txt"):
    v1, v2, w = s.split()
    v1, v2, w = int(v1), int(v2), float(w)
    W[v1][v2] = w                            # сначала знаем только сами рёбра
    vertices.add(v1)
    vertices.add(v2)

for k in vertices:                           # разрешаем ходить через вершину k
    for i in vertices:
        for j in vertices:
            if W[i][k] + W[k][j] < W[i][j]:
                W[i][j] = W[i][k] + W[k][j]

print(W[1][100])                             # обычный кратчайший
print(W[1][486] + W[486][100])               # обязательно через вершину 486

B = [[INF] * 1001 for _ in range(1001)]      # та же таблица, но без вершины 670
for s in open("graph.txt"):
    v1, v2, w = s.split()
    v1, v2, w = int(v1), int(v2), float(w)
    if v1 != 670 and v2 != 670:
        B[v1][v2] = w

for k in vertices:
    for i in vertices:
        for j in vertices:
            if B[i][k] + B[k][j] < B[i][j]:
                B[i][j] = B[i][k] + B[k][j]

print(B[1][100])                             # в обход вершины 670

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

30.799999999999997
40.9
78.0

Через 486 путь длиннее обычного — так и должно быть: лишнее требование не может помочь.

Запрет вершины 670 стоит дороже всего: она лежала на кратчайшем пути, и без неё остаётся единственная дорога 1 → 810 → 100.

Ловушки

Написали W[1][X] + W[100][X]. Второй кусок идёт из X в сотню, а не наоборот.
Запретили вершину, но выбросили только выходящие из неё рёбра.
Посчитали обычный кратчайший путь и обрадовались, что он и так проходит через X. Проверять надо, а не надеяться.
Сложили две бесконечности и напечатали inf. Значит, такого пути через X просто нет.

Проверь себя

Файл graph.txt: сопоставьте вершину и длину кратчайшего пути из 1 в 100 через неё.

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

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

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

Attached files
graph.txt

Печать