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