Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313089
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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–7–100$ (длина $7,5$) единственный, остальные пути длиннее.
Функция возвращает пару (длина кратчайшего пути из $v$ в $100$, число таких путей). При переборе рёбер $v → u$ возможны три случая: путь через $u$ короче найденного — запоминаем новую длину и берём счётчик $u$; такой же длины — прибавляем счётчик $u$; длиннее — пропускаем. База: ($0, 1$) для вершины $100$. Тупик автоматически даёт ($+∞, 0$) и на счёт не влияет.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_10.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, 1)
best, cnt = float('inf'), 0
for u, w in g.get(v, []):
L, c = f(u)
if w + L < best: # нашли путь короче — счётчик заново
best, cnt = w + L, c
elif w + L == best: # ничья — добавляем
cnt += c
return (best, cnt)
print(f(1)[1])Второй способ — сначала найти длину кратчайшего пути d(1), затем посчитать число путей ровно такой длины рекурсией с двумя параметрами (как в задании 8, но «остаток» — длина, а не число рёбер):
@lru_cache(None)
def d(v): # длина кратчайшего пути v -> 100
if v == 100:
return 0
return min([w + d(u) for u, w in g.get(v, [])], default=float('inf'))
@lru_cache(None)
def cnt(v, rest): # число путей v -> 100 длиной ровно rest
if v == 100:
return 1 if rest == 0 else 0
return sum(cnt(u, rest - w) for u, w in g.get(v, []) if rest - w >= 0)
print(cnt(1, d(1)))Длина кратчайшего пути $62,0$; пять путей: $1 → 351 → 776 → 927 → 914 → 100; 1 → 351 → 356 → 172 → 292 → 914 → 100; 1 → 330 → 91 → 277 → 292 → 914 → 100; 1 → 330 → 344 → 213 → 971 → 927 → 914 → 100; 1 → 330 → 541 → 277 → 292 → 914 → 100$.
20
