Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313033
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером $1$ в вершину с номером $100$, проходящего через вершину с номером $790$. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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 |
Для приведённого примера при условии прохождения через вершину $4$ верным ответом будет $10$ (единственный такой путь $1–4–100$ имеет длину $10,5$).
Любой путь из $1$ в $100$, проходящий через $K$, распадается на две части: $1 → … → K$ и $K → … → 100$. В ациклическом графе эти части не могут иметь общих вершин, кроме $K$, поэтому минимальная длина всего пути равна сумме минимальных длин частей: $d(1, K) + d(K, 100)$. Достаточно написать одну функцию «кратчайший путь из src в dst» и вызвать её дважды.
Первый способ
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_4.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))
def short(src, dst): # длина кратчайшего пути src -> dst
@lru_cache(None)
def f(v):
if v == dst:
return 0
best = float('inf') # тупик: пути нет
for u, w in g.get(v, []):
best = min(best, w + f(u))
return best
return f(src)
K = 790
print(int(short(1, K) + short(K, 100)))Второй способ — два запуска алгоритма Дейкстры (из $1$ и из $K$). Словарь $g$ при этом должен содержать все вершины, в том числе те, что встречаются только как конец ребра:
import heapq
g = {}
for line in open('23_4.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, []) # все вершины должны быть ключами
def dijkstra(src): # словарь расстояний от src
d = {v: float('inf') for v in g}
d[src] = 0
q = [(0, src)]
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))
return d
K = 790
print(int(dijkstra(1)[K] + dijkstra(K)[100]))$d(1, 790) = 11989,8; d(790, 100) = 2854,1$; сумма $14843,9$. Путь: $1 → 321 → 664 → 656 → 388 → 790 → 227 → 100$ ($7$ рёбер).
20
