0-K BFS

Материал из Algocode wiki
Версия от 09:09, 19 сентября 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Эта страница содержит алгоритм 1-k BFS. Алгоритм 0-k BFS отличается от него только тем, что встречая рёбра веса 0, нам надо добавлять их в голову текущей очереди.

1-k BFS

Задача: вам дан взвешенный граф $G$, веса рёбер которого принимают значения от $1$ до $k$ и выделена вершина $s$ в нём. Вас просят найти в этом графе кратчайшие расстояния от $s$ до всех остальных вершин.

Наблюдение

Поскольку в графе нет рёбер отрицательного веса, то максимальное кратчайшее расстояние в нём равно $(|V| - 1) \times k$.

Предложение 1

Давайте для каждого расстояния $d$ заведём $atdist[d]$ -- очередь вершин, которые находятся на таком расстоянии от $s$ плюс, возможно, некоторые вершины, до которых существует путь длины $d$ от $s$, но для которых существует более короткий путь. Получится $(|V| - 1) \times k$ списков.

Как посчитать эти списки?

База

$atdist[0] = {s}$

Шаг

Если вершина $v$ лежит в списке $atdist[d]$, то любой из её ранее непосещённых соседей, достижимых по ребру веса $w$ лежит в списке с номером не более $atdist[d+w]$. Давайте тогда её добавим в этот список. Однако, надо помнить, что на самом деле кратчайшее расстояние до неё может быть и меньше, чем [d+w].

Теорема

Если для всех вершин до уровня $d$ расстояния посчитаны корректно, то на уровне $d+1$ сейчас находятся те вершины, до которых расстояние равно $d+1$ плюс, возможно, дубликаты вершин, до которых мы в какой-то момент нашли путь длины $d+1$, а затем нашли более короткий (разумеется, более длинные пути мы не будем рассматривать).

Доказательство: по индукции.

А нужно ли нам так много списков?

Заметим, что на самом деле мы можем обойтись $k+1$ списками, поскольку обрабатывая рёбра, мы никогда не уходим вперёд на более, чем $k$ очередей, а старые очереди мы тем более не используем. Поэтому вместо добавления в $atdist[d+w]$ мы будем добавлять в $atdist[(d+w) \mod (atdist.size())]$.

Сложность алгоритма

$O(k|V| + |E|)$, поскольку после первого добавления вершины в какую-либо очередь, в другие очереди мы сможем добавить её не более $k-1$ раз.



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

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