Кратчайшее расстояние между двумя вершинами: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Как это закодить? Надо просто вместо вершины, хранить пару -- (текущая вершина, стартовая вершина), а в начале алгоритма закинуть в очередь пары $(v, v)$ и $(u, u)$. | Как это закодить? Надо просто вместо вершины, хранить пару -- (текущая вершина, стартовая вершина), а в начале алгоритма закинуть в очередь пары $(v, v)$ и $(u, u)$. | ||
| + | |||
| + | {{Автор|Александр Гришутин|rationalex}} | ||
Текущая версия на 22:52, 18 ноября 2019
Задача
Предположим, нам надо найти кратчайший путь между двумя вершинами $u$ и $v$ в графе, в котором довольно много рёбер. Обычный BFS, запущенный из $u$ в худшем случае пройдёт все рёбра, прежде, чем найдёт $v$. Хочется попробовать ускорить процесс, ведь мы знаем, в какую вершину мы хотим попасть.
Идея
Для этого можно запустить BFS сразу из двух вершин, ведя его как бы параллельно, сначала обрабатывая вершины на расстоянии 1 от хотя бы одной из стартовых, затем на расстоянии 2 итд. Тогда первая вершина, до которой дойдут обе 'волны' и будет той, через которую будет проходить кратчайший путь.
Как это закодить? Надо просто вместо вершины, хранить пару -- (текущая вершина, стартовая вершина), а в начале алгоритма закинуть в очередь пары $(v, v)$ и $(u, u)$.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex