Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313151
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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 |
Для приведённого примера верным ответом будет $1$: путь $1–100$ состоит из одного ребра (веса рёбер в этом вопросе не учитываются).
Это кратчайший путь в графе, где каждое ребро весит $1$: веса из файла не читаются, а в переходе вместо $w + f(u)$ стоит $1 + f(u)$. Второй способ — поиск в ширину: при обходе по слоям первое посещение вершины происходит по пути с наименьшим числом рёбер.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_15.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # вес ребра не нужен
g.setdefault(a, []).append(b)
@lru_cache(None)
def f(v): # наименьшее число рёбер v -> 100
if v == 100:
return 0
best = float('inf')
for u in g.get(v, []):
best = min(best, 1 + f(u)) # каждое ребро «весит» 1
return best
print(f(1))Второй способ — поиск в ширину (продолжение после чтения графа):
from collections import deque
dist = {1: 0} # поиск в ширину из вершины 1
q = deque([1])
while q:
v = q.popleft()
for u in g.get(v, []):
if u not in dist: # первое посещение — кратчайшее
dist[u] = dist[v] + 1
q.append(u)
print(dist[100])Путей из пяти рёбер в этом файле пять (совпадение с ответом случайно). Кратчайший по сумме весов путь (длина $12607,9$) состоит из $6$ рёбер, самый длинный по числу рёбер путь — из $26$.
20
