Алгоритм Форда-Беллмана
Содержание
Задача
Дан ориентированный граф $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 = 0; k < vertices_count; ++k) {
for (auto&& [u, v, w] : edges) {
relax(sp[k][v], sp[k-1][u] + 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)
Заметим следующее:
- Если на какой-то итерации внешнего цикла $sp[*]$ не изменился, то мы уже нашли все кратчайшие расстояния и можно прекратить наш алгоритм.
- Достаточно на каждом шаге рассматривать не все рёбра, а только те, у которых $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$ пойдя из конца ребра мы вернёмся в него, пройдя по нашему циклу отрицательного веса.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex