Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313275
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Гарантируется, что для каждой вершины, достижимой из вершины с номером $1$, кратчайший путь из вершины $1$ в эту вершину единственный. Найдите и запишите в ответе количество вершин, для которых кратчайший путь из вершины $1$ в эту вершину проходит через вершину с номером $144$ (сама вершина $144$ также учитывается). Под длиной пути понимается сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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$ верным ответом будет $3$: через вершину $7$ проходят кратчайшие пути из $1$ в вершины $7$ (длина $5,5$), $100$ ($7,5$; путь $1–7–100$) и $12$ ($8,5$; путь $1–7–100–12$). При вершине $4$ ответ $1$ — только сама вершина $4$.
Кратчайшие пути из вершины $1$ во все вершины образуют дерево: у каждой достижимой вершины есть «родитель» — предпоследняя вершина её кратчайшего пути. Алгоритм Дейкстры строит это дерево, если при каждом улучшении $d[u]$ запоминать $par[u] = v.$ Тогда вершина $v$ «проходит через $K$», если, поднимаясь от $v$ по родителям, мы встретим $K$ раньше, чем корень $1$. Ответ — размер поддерева вершины $K$.
import heapq
g = {} # вершина -> список (сосед, вес)
for line in open('23_22.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, []) # все вершины — ключи словаря
K = 144
d = {v: float('inf') for v in g} # Дейкстра из 1 + родители
par = {}
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
par[u] = v # кратчайший путь в u приходит из v
heapq.heappush(q, (d[u], u))
k = 0
for v in g:
if d[v] == float('inf'): # недостижимые не считаем
continue
x = v
while x != 1 and x != K: # поднимаемся по дереву к корню
x = par[x]
if x == K: # по дороге встретили K
k += 1
print(k)Второй способ — через расстояния: кратчайший путь в $v$ проходит через $K$ тогда и только тогда, когда $d(1, v) = d(1, K) + d(K, v)$. Сравнивать нужно с допуском: суммы одних и тех же весов, посчитанные в разном порядке, отличаются в последних знаках (продолжение после чтения графа и import heapq):
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 = 144
d1, dK = dijkstra(1), dijkstra(K)
k = 0
for v in g:
if d1[v] < float('inf') and dK[v] < float('inf'):
if abs(d1[v] - (d1[K] + dK[v])) < 1e-6: # с допуском, не через ==
k += 1
print(k)Через вершину $144$ (расстояние от $1$ равно $10251,4$) проходят кратчайшие пути в вершины $100, 144, 172, 214, 226, 442, 445, 745, 758, 769$.
20
