Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 8. Графы. Поиск кратчайшего пути. Алгоритм Форда-Беллмана.

Пусть дан взвешенный ориентированный граф с N вершинами и M ребрами. Требуется найти кратчайшие расстояния от данной вершины s до всех остальных. Эта задача может быть решена с помощью алгоритма Форда-Беллмана.

В основе алгоритма Форда-Беллмана лежит метод динамического программирования. Пусть w_i,j - длина дуги из вершины i в вершину j или бесконечность, если такой дуги нет. Пусть A_n,m - длина кратчайшего пути из начальной вершины в вершину m, проходящего не более чем по n ребрам. Пусть k - предыдущая вершина в этом пути. Тогда A_n,m=A_n-1,k + w_k,m. Значит A_n,m = min(A_n-1,m, min{1<=i<=N}(A_n-1,i+w_i,m)) (*).

Значения A_0,i равны бесконечности для всех i, отличных от s, A_0,s=0.

Будем считать A_i,j в порядке неуменьшения i, а при равных i - в порядке увеличения j. Тогда для вычисления i-й строки матрицы A нам необходимо знать только i-1-ую ее строку. Ответом на нашу задачу является N-я строка, значит, на каждом шаге можно хранить только предыдущую строку матрицы.

При такой реализации алгоритм будет выполнять порядка N³ операций.

Заметим, что при вычислении следующей строки матрицы по предыдущей каждую дугу графа мы рассмотрели ровно 1 раз. Воспользуемся этим, чтобы немного ускорить наш алгоритм. Пусть у нас известна n-1 строка матрицы A. Скопируем ее в n-ую строку. Далее рассмотрим все дуги нашего графа (x,y) и изменим A_n,y согласно формуле: A_n,y = min(A_n,y,A_n-1,x+w_x,y) (**). Теперь у нас посчитана n-я строка матрицы A.

При такой реализации алгоритм выполнит порядка NM действий.

Восстановление пути
Пусть в формуле (*) в ходе работы алгоритма Форда-Беллмана минимум достигается при i=k или в формуле (**) на дуге (m,k). Тогда запишем в d_m значение k. В конце работы алгоритма мы получим, что для каждой вершины i в d_i хранится номер предыдущей вершины в кратчайшем пути от s до i. По массиву d легко восстановить путь.

Нахождение вершин, до которых существует сколь угодно короткий путь
Сравним a_n,i и a_2n,i. Если a_n,i > a_2n,i, то до вершины i существует сколь угодно короткий путь. Иначе - нет.