37. Метод Форда и Беллмана нахождения расстояний от вершины - “источника” до остальных вершин. Временная сложность алгоритма. Алгоритм восстановления кратчайшего пути по известным расстояниям. Временная сложность алгоритма

 

Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. 

 

Формулировка задачи

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

 

Решение задачи на графе без отрицательных циклов

Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.

Для нахождения кратчайших путей от одной вершины до всех остальных, воспользуемся методом динамического программирования. Построим матрицу Aij, элементы которой будут обозначать следующее: Aij — это длина кратчайшего пути из s в i, содержащего не более j рёбер.

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и +\infty в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из j − 1 ребра, к которому добавлено последнее ребро. Если про пути длины j − 1все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

 

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

 

for v \in V

  do d[v] \gets +\infty

d[s] \gets 0

for i \gets 1 to  | V |  − 1

  do for (u, v) \in E

    if d[v] > d[u] + w(u,v)

      then d[v] \gets d[u] + w(u, v)

return d

 

Здесь V — множество вершин графа G, E — множество его рёбер, а w — весовая функция, заданная на ребрах графа.

Внешний цикл выполняется |V| - 1 раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.

Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу Pij.

Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).

 

Теперь алгоритм Беллмана — Форда выглядит так:

 

for v \in V

  for i \gets 0 to  | V |  − 1

    do A_{vi} \gets +\infty

A_{s0} \gets 0

for i \gets 1 to  | V |  − 1

  do for (u, v) \in E

    if Avi > Au,i − 1 + w(u,v)

      then A_{vi} \gets A_{u, i-1} + w(u, v)

           P_{vi} \gets u

После выполнения этого алгоритма элементы Ai,j содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:

while j > 0

  p[j] \gets i

  i \gets P_{ij}

  j \gets j - 1

return p

 

Граф с отрицательными циклами

Алгоритм Беллмана — Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не |V| - 1, a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию. Можно отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит можно сделать выход из цикла.

 

 

Пусть мы знаем кратчайшие расстояния до всех вершин. Как найти кратчайший путь до конкретной вершины? Рассмотрим эту вершину (обозначим ее V). Пусть длина пути до нее L. Эта вершина является последней в пути к V. Найдем какую-нибудь вершину, которая соединена с V, и расстояние до которой равно L-1. Тогда эта вершина является предпоследней в пути (если таких вершин несколько, значит, существует несколько кратчайших путей и можно выбрать любую из этих вершин). Далее найдем вершину, которая соединена с предпоследней и расстояние до которой равно L-2. Она является пред-предпоследней. Продолжая этот процесс, мы можем "раскрутить" весь путь задом наперед. Осталось только запомнить его в массиве и вывести в правильном порядке.