Между населёнными пунктами построены дороги, их протяжённость (стоимость) дана в таблице. Двигаться можно только по дорогам из таблицы. Нужно найти длину кратчайшего пути из одного пункта в другой. Удобно нарисовать граф и последовательно находить кратчайшие расстояния до всех пунктов (алгоритм Дейкстры на бумаге).
Условие
Дороги и их длины: А–Б 2, А–В 5, Б–В 1, Б–Г 7, В–Г 2, В–Д 6, Г–Д 1, Г–Е 5, Д–Е 2. Определите длину кратчайшего пути из А в Е.
Решение
До Б — 2, до В — 2 + 1 = 3 (короче прямой 5), до Г — 3 + 2 = 5, до Д — 5 + 1 = 6 (короче, чем 3 + 6), до Е — 6 + 2 = 8 (короче, чем 5 + 5). Ответ: 8, путь А–Б–В–Г–Д–Е.
import heapq
roads = {('А', 'Б'): 2, ('А', 'В'): 5, ('Б', 'В'): 1, ('Б', 'Г'): 7, ('В', 'Г'): 2,
('В', 'Д'): 6, ('Г', 'Д'): 1, ('Г', 'Е'): 5, ('Д', 'Е'): 2}
g = {}
for (a, b), w in roads.items():
g.setdefault(a, []).append((b, w))
g.setdefault(b, []).append((a, w))
dist, q = {'А': 0}, [(0, 'А')]
while q:
d, v = heapq.heappop(q)
for u, w in g[v]:
if d + w < dist.get(u, 10**9):
dist[u] = d + w
heapq.heappush(q, (d + w, u))
print(dist['Е'])
Код на Python 3 — его можно запустить прямо на ИнфДоске.
В банке ИнфДоски 91 задание этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.