Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313057
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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–7–100$ имеет длину $7,5$ и состоит из двух рёбер, поэтому верным ответом будет $2$.
Рекурсия та же, что для длины кратчайшего пути, но функция возвращает пару (длина, число рёбер). Кортежи в Python сравниваются лексикографически: сначала по длине, при равенстве — по числу рёбер, поэтому $min$ по парам находит именно кратчайший по весу путь, а вторая компонента — количество его рёбер. Единственность кратчайшего пути гарантирует однозначность ответа. Тот же приём с кортежем (длина, путь) восстанавливает и сам путь.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_6.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 f(v): # (длина, число рёбер) кратчайшего пути v -> 100
if v == 100:
return (0, 0)
best = (float('inf'), 0)
for u, w in g.get(v, []):
L, k = f(u)
best = min(best, (w + L, k + 1)) # пары сравниваются по длине, затем по числу рёбер
return best
print(f(1)[1])Вариант с восстановлением пути:
@lru_cache(None)
def f(v): # (длина, кортеж вершин) кратчайшего пути v -> 100
if v == 100:
return (0, (100,))
best = (float('inf'), ())
for u, w in g.get(v, []):
L, p = f(u)
best = min(best, (w + L, (v,) + p))
return best
L, path = f(1)
print(path) # сам путь — удобно для проверки
print(len(path) - 1) # рёбер на одно меньше, чем вершинКратчайший путь длиной $14722,4$: $1 → 785 → 650 → 753 → 903 → 913 → 727 → 62 → 255 → 100$ — десять вершин, девять рёбер.
20
