0-K BFS: различия между версиями
KiKoS (обсуждение | вклад) м |
|||
Строка 1: | Строка 1: | ||
− | =Эта страница содержит алгоритм 1-k BFS. Алгоритм 0-k BFS отличается от него только тем, что встречая рёбра веса 0, нам надо добавлять их в голову текущей очереди.= | + | ===Эта страница содержит алгоритм 1-k BFS. Алгоритм 0-k BFS отличается от него только тем, что встречая рёбра веса 0, нам надо добавлять их в голову текущей очереди.=== |
=1-k BFS= | =1-k BFS= |
Версия 15:37, 17 ноября 2019
Содержание
Эта страница содержит алгоритм 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(|V| + k|E|)$, поскольку ответ для каждого из концов рёбер мы можем прорелаксировать (найти более оптимальный ответ) и добавить в другую очередь не более $k$ раз.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex