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

Задача

Дан граф $G=(V, E)$ с выделенной вершиной $s$. Веса рёбер в графе могут быть любыми. Надо для каждой вершины найти кратчайшее расстояние до неё от $s$.

Динамическое программирование

Решим эту задачу с помощью динамического программирования:

• $sp[k][v]$ - кратчайшее растояние от $s$ до $v$ по путям, в которых $k$ рёбер.
• Начальные значения
  • $ sp[0][s] = 0 $
  • $ sp[0][V \ s] = INF $
  • $ sp[1...|V|][*] = INF $
• $ sp[k][v] = \min_{u \in N(v)} sp[k-1][u] + w(u, v) $
• Порядок пересчёта:

 
for (int k = 0; k < vertices_count; ++k) {
  for (int v = 0; v < vertices_count; ++k) {
    // ...
  }
}

• Ответ: dist[v] = \min_{k} sp[k][v]
• Восстановление ответа: либо запоминаем для каждого состояния, из какого пришли, либо заново перебираем

Переходим от вершин к рёбрам

Заметим, что цикл по вершинам, внутри которого перебираются соседи, можно заменить на цикл по рёбрам и получить

 
void relax(int& old_value, int new_value) {
  old_value = min(old_value, new_value);
}

// Инициализация динамики
for (int k = 0; k < vertices_count; ++k) {
  for (auto&& [u, v, w] : edges) {
    relax(sp[k][u], sp[k-1][v] + w);
    relax(sp[k][v], sp[k-1][u] + 1); 
  }
}

Избавляемся от одного из измерений

Мы получили решение, в котором используется массив размера $|V| \times |V|$. Мы можем изменить это и получить 2 массива длины $|V|$ - достаточно заметить, что для подсчёта $sp[k][*]$ достаточно знать $sp[k-1][*]$, поэтому нам достаточно хранить только 2 последних слоя динамики.

Оставляем только один массив

В предыдущем пункте можно отказаться от двух массивов и оставить только $sp[v]$. Тогда $sp[v] = \min_{u \in N(v)} sp[u] + w(u, v)$. Однако, теперь значение, хранящееся в $sp[v]$ потеряет то значение, которое мы ему придавали раньше, потому что теперь при пересчёте слоя динамики мы можем воспользоваться значениями из нового слоя.

Однако можно доказать, что за $k$ итераций в $sp[v]$ будут точно рассмотрены пути длины хотя бы $k$ рёбер от $s$ до $v$ (плюс, возможно, пути большей длины) (доказательство по индукции, упражнение читателю). Из этого следует, что за $|V| - 1$ итераций в $sp[v]$ будут рассмотрены все возможные пути из $s$ в $v$ $\implies$ в $sp[v]$ будут будет хранится кратчайшее расстояние от $s$ до $v$.

Ускоряем алгоритм

Заметим следующее:

1. Если на какой-то итерации внешнего цикла $sp[*]$ не изменился, то мы уже нашли все кратчайшие расстояния и можно прекратить наш алгоритм.
2. Достаточно на каждом шаге рассматривать не все рёбра, а только те, у которых $sp$ изменился хотя бы для одного из концов.

Эти немудрёные рассуждения приводят нас к следующему, окончательному коду:

 
#typedef Vertex int

bool try_relax(int& old_value, int new_value) {
  old_value = min(old_value, new_value);
  return old_value == new_value;
}

vector<int> FordBellmanShortestPaths(int start) {
  // Инициализация sp
  vector<Vertex> updated_vertices = {start};

  for (int k = 0; k < vertices_count; ++k) {
    vector<Vertex> newly_updated_vertices;

    for (auto& v : updated_vertices) {
      for (auto&& [to, w] : edge_from[v]) {
        if (try_relax(sp[to], sp[v] + w)) {
          newly_updated_vertices.push_back(to);
        }
      }
    }
    
    if (newly_updated_vertices.empty()) {
      break;
    }

    updated_vertices.swap(newly_updated_vertices); 
  }

Поиск циклов отрицательного веса

Лемма

В графе есть цикл отрицательного веса $\iff$ на $|V|$-й итерации алгоритма $updated_vertices$ непусто.

Доказательство:

$\impliedby$: очевидно

$\implies$: тривиально

Из леммы следует, что для проверки наличия цикла отрицательного веса достаточно запустить алгоритм на ещё одну итерацию и проверить, что ничего не изменилось.

Восстановление цикла отрицательного веса

Чтобы восстановить цикл достаточно для каждой вершины $v$ запоминать $prev[v]$ - вершину, через которую произошла последняя релаксация ребра в $v$. Тогда для восстановления цикла отрицательного веса достаточно взять любое из рёбер, которые прорелаксировались на $|V|$-м шаге и начать от них разматывать цикл.

Корректность этого алгоритма следует из того, что любое ребро, которое прорелаксировалось на $|V|$-м шаге лежит на цикле отрицательного веса $\implies$ пойдя из конца ребра мы вернёмся в него, пройдя по нашему циклу отрицательного веса.

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex