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

Материал из Algocode wiki
Перейти к: навигация, поиск

Задача

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

Ориентированность

Ориентированность графа важна, потому что поиск кратчайших путей в неориентированном графе с отрицательными весами рёбер не решается с помощью алгоритма Форда-Беллмана. Но можно свести к поиску паросочетания минимальной стоимости в графе (необязательно двудольном). Подробнее можно почитать тут

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

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

  • $sp[k][v]$ - кратчайшее растояние от $s$ до $v$ по путям, в которых $k$ рёбер.
  • Начальные значения
    • $ sp[0][s] = 0 $
    • $ sp[0][V \setminus \{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; ++v) {
    // ...
  }
}
  • Ответ: $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 = 1; k < vertices_count; ++k) {
  for (auto [from, to, w] : edges) {
    relax(sp[k][to], sp[k-1][from] + w); 
  }
}

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

Мы получили решение, в котором используется массив размера $|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$.

Ускоряем алгоритм (Алгоритм SPFA)

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

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

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

 
typedef int Vertex;
typedef long long dist_t;

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

vector<dist_t> SPFA(int start) {
  vector<dist_t> sp(n, INF);
  sp[start] = 0;
  
  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); 
  }

 return sp;
}

Форд-Беллман с random_shuffle

Если вы вдруг забыли про SPFA, то вы всё ещё можете ускорить ваш алгоритм Форда-Беллмана, случайным образом перемешивая рёбра. Подробнее: http://codeforces.com/blog/entry/58825

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

Теорема

В графе есть цикл отрицательного веса, достижимый из $s$ $\iff$ после $|V|$-й итерации алгоритма $updated \_ vertices$ непусто.

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


$\implies$: пусть в графе есть отрицательный цикл $v_0 \rightarrow v_1 \rightarrow \dots \rightarrow v_k = v_0$. Если в этом цикле есть такое ребро $v_i \rightarrow v_{i+1}$, что на $|V|$-м шаге $sp[v_{i+1}] > sp[v_{i}] + w(v_{i}, v_{i+1})$, то $v_{i+1}$ окажется в $updated\_ vertices$ и утверждение доказано. Пусть такого ребра нет, то есть $$ \forall i \in [0 \dots k]: sp[v_{i+1}] \leq sp[v_{i}] + w(v_{i}, v_{i+1}) $$

Сложим эти неравенства и заметим, что $\sum_{0 \leq i \leq k-1} sp[v_{i+1}] = \sum_{0 \leq i \leq k-1} sp[v_{i}]$ (поскольку это одна и та же сумма, в которой сделали циклический сдвиг (помним, что $v_k = v_0$)).

Значит, если сократить, получится: $$ 0 \leq \sum_{0 \leq i \leq k-1} w(v_{i}, v_{i+1}) $$

Или, другими словами, наш цикл вовсе не имеет отрицательный вес. Противоречие.

$\impliedby$: если на $|V|$-й итерации расстояние до какой-то вершины уменьшилось, значит существует последовательность из хотя бы $|V|$ рёбер из $s$ в некоторую вершину $v$, вдоль которой расстояние меньше, чем то, что было на $(|V| - 1)$-й итерации. Поскольку рёбер не меньше, чем $|V|$, то в этой последовательности есть цикл. Если этот цикл имеет неотрицательный вес, то его можно выкинуть из последовательности и получить последовательность рёбер меньшей длины, которая должна была быть рассмотрена на предыдущих шагах алгоритма $\implies$ на $|V|$-й итерации расстояние не могло уменьшиться вдоль последовательности с циклом. Значит, цикл всё-таки имеет отрицательный вес, а это ровно то, чего мы хотели. ∎


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

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

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

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

Как определить кратчайшие расстояния до всех вершин с учётом отрицательных циклов

Запускаем алгоритм на $|V|$ шагов. Если на последнем шаге до вершины расстояние не поменялось, то оно и кратчайшее. Если поменялось, то до неё и до всех вершин, достижимых из неё, расстояние от стартовой вершины равно минус бесконечности. Чтобы найти все вершины с расстоянием минус бесконечность, достаточно запустить dfs из всех вершин, расстояние до которых уменьшилось на последней итерации алгоритма.



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

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