Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313209
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины второго по длине пути из вершины с номером $1$ в вершину с номером $100$, то есть кратчайшего среди всех путей, отличных от кратчайшего. Гарантируется, что кратчайший путь единственный и что существует хотя бы один другой путь. Под длиной пути понимается сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000, M ≤ 1000; W ≤ 10 000$. Количество строк в файле не превосходит $200$. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
| 100 6 6 1 7 4 1 1 | 12 7 1 7 100 100 100 4 | 1.0 7.0 1.0 5.5 2.0 8.0 12.0 2.5 |
Для приведённого примера длины путей равны $7,5$ ($1–7–100$), $10,5$ ($1–4–100$) и $12,0$ ($1–100$); второй по длине путь имеет длину $10,5$, поэтому верным ответом будет $10$.
Функция возвращает две лучшие длины: $f(v) = (l1, l2)$ — кратчайший и второй по длине пути из $v$ в $100$. Кандидаты для $v$ — продолжения через каждого соседа $u$ как лучшего, так и второго пути из $u$: $w + l1(u)$ и $w + l2(u)$. Из всех кандидатов берутся два наименьших. Второй путь из $v$ может отличаться от кратчайшего либо первым ребром, либо продолжением после него — оба случая учтены. База: из вершины $100$ ровно один (пустой) путь, второго нет — ($0, +∞$).
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_18.txt'):
s = line.split() # любые пробелы и табуляции
if len(s) < 3: # пустая строка
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
g.setdefault(a, []).append((b, w))
INF = float('inf')
@lru_cache(None)
def f(v): # (кратчайший, второй) путь v -> 100
if v == 100:
return (0, INF) # из 100 в 100 путь один
cand = []
for u, w in g.get(v, []):
a, b = f(u)
cand.append(w + a) # продолжить лучший путь потомка
cand.append(w + b) # ...или второй по длине
cand.sort()
cand += [INF, INF] # если кандидатов меньше двух
return (cand[0], cand[1])
print(int(f(1)[1]))Второй способ — через удаление рёбер: второй по длине путь отличается от кратчайшего хотя бы одним ребром, поэтому он равен минимуму по всем рёбрам кратчайшего пути от длины кратчайшего пути без этого ребра (продолжение после определения INF):
@lru_cache(None)
def sp(v): # (длина, кортеж вершин) кратчайшего
if v == 100:
return (0, (100,))
best = (INF, ())
for u, w in g.get(v, []):
L, p = sp(u)
best = min(best, (w + L, (v,) + p))
return best
L1, path = sp(1)
best = INF
for i in range(len(path) - 1):
a, b = path[i], path[i + 1] # запрещаем ребро a -> b
@lru_cache(None)
def d(v): # кратчайший путь без ребра a -> b
if v == 100:
return 0
return min([w + d(u) for u, w in g.get(v, [])
if not (v == a and u == b)], default=INF)
best = min(best, d(1))
print(int(best))Кратчайший путь $1 → 889 → 856 → 225 → 806 → 4 → 842 → 100$ имеет длину $12720,4$; второй по длине путь $1 → 889 → 856 → 225 → 291 → 312 → 842 → 100$ — длину $12724,7$.
20
