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 рёбер работает мгновенно, а писать почти нечего.

Способ 1 — алгоритм Беллмана–Форда — Задание 23 ЕГЭ 2027 | Методички — Профиматика