Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #312908
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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$.
Что важно вычитать из условия, прежде чем писать код:
- граф ориентированный и ациклический ($DAG$), веса положительные — значит, подходит любой из трёх стандартных инструментов: динамика по ациклическому графу (рекурсия с запоминанием), алгоритм Дейкстры, релаксация рёбер (Беллман–Форд);
- номера вершин не идут подряд ($L,M≤1000$), поэтому граф удобнее хранить в словаре, а не в списке по индексам;
- разделители — произвольное число пробелов и табуляций, поэтому строки разбираем через split() без аргументов;
- веса вещественные, читаем через float(); в ответ идёт целая часть, при положительных весах int() её и даёт;
- рёбер не более $200$, так что вопрос эффективности не стоит — важна корректность;
- существование пути гарантируется, обработка «пути нет» не нужна.
Проверка на примере из условия. Из $1$ в $100$ ведут три пути: $1→7→100$ длиной $5,5+2,0=7,5$; $1→100$ напрямую длиной $12,0$; $1→4→100$ длиной $2,5+8,0=10,5$. Минимум $7,5$, целая часть $7$. Рёбра $6→7$, $6→1$, $100→12$ на ответ не влияют.
Способ 1: рекурсия по ациклическому графу с запоминанием (динамическое программирование)
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # словарь: вершина -> список (сосед, вес)
for line in open('demo_23.txt'):
s = line.split() # 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 f(v): # длина кратчайшего пути из v в 100
if v == 100:
return 0
best = float('inf')
for u, w in g.get(v, []):
best = min(best, w + f(u))
return best
print(int(f(1))) # целая часть длиныАльтернатива — алгоритм Дейкстры (в приложенном файле дан в комментарии). Для контроля я прогнал три разных алгоритма, все дали одно и то же.
Способ 2: алгоритм Дейкстры с очередью с приоритетом
import heapq
g = {}
for line in open('demo_23.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}
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))
print(int(d[100]))
20
