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