Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313140
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите вершину, достижимую из вершины с номером $1$, для которой длина кратчайшего пути из вершины $1$ в эту вершину наибольшая. Гарантируется, что такая вершина единственная. В ответе запишите номер этой вершины. Под длиной пути понимается сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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$ таковы: в вершину $4 — 2,5$; в вершину $7 — 5,5$; в вершину $100 — 7,5$; в вершину $12 — 8,5$. Наибольшая из них — $8,5$, поэтому верным ответом будет $12$.
Алгоритм Дейкстры за один запуск даёт расстояния от вершины $1$ до всех вершин — остаётся выбрать максимум среди конечных. Две тонкости: словарь $g$ должен содержать все вершины, включая те, у которых нет исходящих рёбер (именно такой оказывается самая удалённая вершина в этом файле), а недостижимые вершины (расстояние $+∞$) из максимума исключаются.
import heapq
g = {}
for line in open('23_13.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))
g.setdefault(b, []) # тупики тоже нужны!
d = {v: float('inf') for v in g} # Дейкстра из 1 во все вершины
d[1] = 0
q = [(0, 1)]
while q:
dv, v = heapq.heappop(q)
if dv > d[v]:
continue
for u, w in g[v]:
if dv + w < d[u]:
d[u] = dv + w
heapq.heappush(q, (d[u], u))
best = max((d[v], v) for v in g if d[v] < float('inf'))
print(best[1]) # номер самой удалённой вершиныВторой способ — рекурсия по обратному графу: $f(v)$ — длина кратчайшего пути из $1$ в $v$ — равна минимуму по всем предшественникам $a$ вершины $v$ величины $f(a) + w(a, v)$, база $f(1) = 0$. Это та же динамика, что раньше, но «задом наперёд»:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
r = {} # обратный граф
verts = set()
for line in open('23_13.txt'):
s = line.split()
if len(s) < 3:
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
r.setdefault(b, []).append((a, w))
verts |= {a, b}
@lru_cache(None)
def f(v): # кратчайший путь 1 -> v
if v == 1:
return 0
best = float('inf')
for a, w in r.get(v, []):|
best = min(best, f(a) + w)
return best
print(max((f(v), v) for v in verts if f(v) < float('inf'))[1])Длина кратчайшего пути из $1$ в $266$ равна $19374,6$; из вершины $1$ достижимы $47$ вершин из $50$; для сравнения, расстояние до вершины $100$ равно $12317,6$.
20
