Алгоритм Форда-Беллмана
Содержание
Задача
Дан граф $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$.
Ускоряем алгоритм
Заметим следующее:
- Если на какой-то итерации внешнего цикла $sp[*]$ не изменился, то мы уже нашли все кратчайшие расстояния и можно прекратить наш алгоритм.
- Достаточно на каждом шаге рассматривать не все рёбра, а только те, у которых $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