Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313483
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Для каждой вершины, лежащей на кратчайшем пути из вершины с номером $1$ в вершину с номером $100$ (кроме самих вершин $1$ и $100$), рассмотрим, на сколько увеличится длина кратчайшего пути из $1$ в $100$, если удалить эту вершину из графа вместе со всеми её рёбрами. Найдите вершину, для которой это увеличение наибольшее. Гарантируется, что кратчайший путь единственный, что после удаления любой такой вершины путь из $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 |
Для приведённого примера кратчайший путь $1–7–100$ (длина $7,5$) содержит единственную промежуточную вершину $7$; после её удаления кратчайшим становится путь $1–4–100$ длиной $10,5$ (увеличение на $3,0$), поэтому верным ответом будет $7$.
Сначала находим кратчайший путь как кортеж вершин (пара «длина, путь»). Затем для каждой его промежуточной вершины считаем кратчайший путь в обход неё — и выбираем вершину с наибольшим приростом. Вершины, не лежащие на кратчайшем пути, рассматривать не нужно: их удаление длину кратчайшего пути не меняет.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_29.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))
@lru_cache(None)
def sp(v): # (длина, кортеж вершин) кратчайшего
if v == 100:
return (0, (100,))
best = (float('inf'), ())
for u, w in g.get(v, []):
L, p = sp(u)
best = min(best, (w + L, (v,) + p))
return best
def short_ban(banned): # кратчайший 1 -> 100 без banned
@lru_cache(None)
def f(v):
if v == banned:
return float('inf')
if v == 100:
return 0
return min([w + f(u) for u, w in g.get(v, [])], default=float('inf'))
return f(1)
d0, path = sp(1)
best = max((short_ban(v) - d0, v) for v in path[1:-1])
print(best[1])Второй способ — алгоритм Дейкстры с пропуском запрещённой вершины (продолжение после нахождения path):
import heapq
def dijkstra(banned): # расстояние 1 -> 100 без banned
d = {v: float('inf') for v in g}
d[1] = 0
q = [(0, 1)]
while q:
dv, v = heapq.heappop(q)
if dv > d[v]:
continue
for u, w in g.get(v, []):
if u == banned:
continue
if dv + w < d.get(u, float('inf')):
d[u] = dv + w
heapq.heappush(q, (d[u], u))
return d.get(100, float('inf'))
d0 = dijkstra(None)
print(max((dijkstra(v) - d0, v) for v in path[1:-1])[1])Кратчайший путь $1 → 712 → 28 → 458 → 917 → 100$ имеет длину $15525,0$. Удаление вершины $712$ увеличивает её на $3469,6$ (до $18994,6$); удаление любой из вершин $28, 458, 917$ — на $272,7$ (до $15797,7$): существует обходной путь, минующий сразу все три.
20
