Задание 23Алгоритмы теории графов

Алгоритм Беллама-Форда

Обновлено 20 октября 2026 г.

Алгоритм Беллмана — Форда

Рассмотрим задачу поиска кратчайшего пути в ориентированном взвешенном графе. Каждому ребру соответствует вес — стоимость перехода между двумя вершинами. Длина пути равна сумме весов всех входящих в него рёбер. Наша цель — найти путь с минимальной суммой весов.

Идея алгоритма

Для каждой вершины будем хранить минимальное расстояние от начальной вершины, которое удалось найти к текущему моменту. Расстояние до самой начальной вершины равно нулю. Для остальных вершин сначала запишем бесконечность: путь до них пока неизвестен. Пусть из вершины L в вершину M ведёт ребро с весом W. Если расстояние до L уже известно, можно попробовать продолжить этот путь до M.

Длина такого пути равна:

d[L] + W.

Сравним её с уже найденным расстоянием до M и оставим меньшее значение:

d[M] = \min(d[M], d[L] + W).

Такое обновление расстояния называется релаксацией ребра. Алгоритм Беллмана — Форда многократно перебирает все рёбра графа и выполняет для каждого из них это действие.

Разберём пример

Найдём кратчайший путь из вершины 1 в вершину 100. Пусть рёбра записаны в файле в следующем порядке:

\begin{array}{c|c|c} L & M & W \\ \hline 7 & 100 & 3 \\ 3 & 7 & 2 \\ 1 & 3 & 4 \\ 1 & 7 & 10 \\ 1 & 100 & 15 \end{array}

До начала работы расстояния имеют следующие значения:

\begin{array}{c|c|c|c} d[1] & d[3] & d[7] & d[100] \\ \hline 0 & \infty & \infty & \infty \end{array}

Первый проход

Рассмотрим ребро из 7 в 100. Расстояние до вершины 7 пока неизвестно, поэтому улучшить расстояние до 100 не получится.

По той же причине ребро из 3 в 7 пока ничего не изменяет.

Следующее ребро ведёт из 1 в 3. До вершины 1 расстояние равно нулю, поэтому получаем:

d[3] = \min(\infty, 0 + 4) = 4.

Затем рассматриваем ребро из 1 в 7:

d[7] = \min(\infty, 0 + 10) = 10.

Наконец, рассматриваем ребро из 1 в 100:

d[100] = \min(\infty, 0 + 15) = 15.

После первого прохода нашли прямые пути из начальной вершины:

\begin{array}{c|c|c|c} d[1] & d[3] & d[7] & d[100] \\ \hline 0 & 4 & 10 & 15 \end{array}

Второй проход

Снова начинаем с первого ребра файла.

Теперь расстояние до вершины 7 известно. Через неё можно добраться до 100 за:

10 + 3 = 13.

Это меньше ранее найденного расстояния 15:

d[100] = \min(15, 10 + 3) = 13.

Далее рассматриваем ребро из 3 в 7. Через вершину 3 можно добраться до 7 за:

4 + 2 = 6.

Улучшаем расстояние:

d[7] = \min(10, 4 + 2) = 6.

Оставшиеся рёбра улучшений не дают:

\begin{array}{c|c|c|c} d[1] & d[3] & d[7] & d[100] \\ \hline 0 & 4 & 6 & 13 \end{array}

Обратим внимание: расстояние до 7 уменьшилось после того, как мы уже проверили ребро из 7 в 100. Поэтому новое значение будет использовано для этого ребра только на следующем проходе.

Третий проход

Снова рассматриваем ребро из 7 в 100:

d[100] = \min(13, 6 + 3) = 9.

Остальные рёбра ничего не меняют. Получаем:

\begin{array}{c|c|c|c} d[1] & d[3] & d[7] & d[100] \\ \hline 0 & 4 & 6 & 9 \end{array}

Найденный путь проходит через вершины:

1 \to 3 \to 7 \to 100.

Его длина равна:

4 + 2 + 3 = 9.

Зачем повторять проходы

Рёбра в файле могут находиться в произвольном порядке. Поэтому найденное улучшение не всегда удаётся сразу передать дальше.

Если бы рёбра из 1 в 3, из 3 в 7 и из 7 в 100 стояли именно в таком порядке, путь длиной 9 нашёлся бы уже за первый проход.

Повторные проходы позволяют получить правильный результат независимо от порядка строк файла.

Сколько проходов нужно

В ациклическом графе путь не может повторно посещать одну и ту же вершину: иначе возник бы цикл.

Поэтому при $V$ вершинах любой путь содержит не более $V - 1$ рёбер. После $V - 1$ полных проходов все кратчайшие расстояния будут найдены.

Иногда достаточно меньшего количества проходов. Если за целый проход ни одно расстояние не изменилось, дальнейший перебор можно прекратить.

Задача из демоверсии 2027

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке.

100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
Для приведённого примера верным ответом будет 7.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Решение

Сначала прочитаем файл. Каждое ребро сохраним в списке a как тройку: начальная вершина, конечная вершина и вес.

Номера вершин преобразуем в целые числа, а веса — в вещественные.

Расстояния будем хранить в списке dp. Индекс элемента соответствует номеру вершины.

По условию номера вершин не превышают 1000, поэтому создадим список из 1001 элемента. Элемент с индексом 0 использовать не будем.

Вместо бесконечности возьмём большое число:

10^{20}.

Оно заведомо больше длины любого пути при ограничениях задачи. Для начальной вершины запишем ноль:

dp[1] = 0.

Затем выполним 1000 проходов по всем рёбрам. Этого достаточно, поскольку в графе не более 1000 вершин.

Для каждого ребра обновим расстояние по формуле:

dp[M] = \min(dp[M], dp[L] + W).

После завершения перебора в dp[100] будет находиться длина кратчайшего пути. Поскольку все веса положительные, для получения целой части достаточно применить int.

В файле не более 200 рёбер, поэтому программа выполнит не более:

1000 \cdot 200 = 200\,000

обновлений расстояний.

Полное решение на Python будет выглядеть так:

f = open('23.txt')
a = []
for s in f:
    l,m,w = s.split()
    a.append((int(l),int(m),float(w)))
dp = [10**20]*1001
dp[1] = 0
for i in range(1000):
    for l,m,w in a:
        dp[m] = min(dp[m],dp[l]+w)
print(int(dp[100]))