4 Способ 1 — алгоритм Беллмана–Форда
Способ 1 — алгоритм Беллмана–Форда
Идея простая. Заведём для каждой вершины расстояние от старта: для вершины 1 оно равно 0, для всех остальных — «бесконечность» (очень большое число). Затем много раз проходим по всем рёбрам и пробуем каждым улучшить расстояние: если через ребро L → M добраться до M короче, чем записано, — обновляем. Достаточно повторить проход столько раз, сколько всего рёбер, — и все расстояния станут кратчайшими.
edges = []
for s in open("23.txt"): # читаем рёбра из файла
a, b, w = s.split()
edges.append((int(a), int(b), float(w)))
INF = 10**10
dist = [INF] * 1001 # расстояния до вершин 0..1000
dist[1] = 0 # старт — вершина 1
for _ in range(len(edges)): # проходим все рёбра столько раз, сколько их
for a, b, w in edges:
if dist[a] + w < dist[b]: # через ребро a->b получилось короче?
dist[b] = dist[a] + w # обновляем расстояние до b
print(int(dist[100])) # целая часть кратчайшего пути до 100Разберём по частям:
edges— список всех рёбер(откуда, куда, вес); читаем прямо из файла построчно.dist— расстояния от вершины 1 до каждой вершины. Номера вершин ≤ 1000, поэтому массива на 1001 хватает.Двойной цикл — это и есть релаксация:
len(edges)раз проходим по всем рёбрам и укорачиваем расстояния.int(dist[100])— берём целую часть длины кратчайшего пути до вершины 100.
Пример: разбор
Условие В файле — ациклический ориентированный взвешенный граф (строки вида «L M W»). Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100. |
Запускаем код на файле из примера: программа печатает 7 (кратчайший путь 1 → 7 → 100 длиной 7.5).
Ответ: 7 |
💡 Почему это надёжно Беллман–Форд не требует, чтобы рёбра шли по порядку, и не боится «неудобной» нумерации вершин. Он просто много раз улучшает расстояния, пока они не станут кратчайшими. Медленнее «умных» алгоритмов, но для 200 рёбер работает мгновенно, а писать почти нечего. |