Bi Directional Dijkstra
1.0.0
Учитывая график с неотрицательным весом края, исходную вершину S и целевой вертез . Найдите кратчайший путь между S и T
Но почему бы нам просто не использовать алгоритм Дейкстры для решения проблемы?
0 (e + vlogv) является худшей сложностью времени времени алгоритма Dijkstra, который довольно быстрый. Но для графика с 20 -миллионными вершинами и 50 миллионами краев он будет работать в среднем в течение нескольких секунд. Итак, нам нужно что -то значительно быстрее.
Прежде чем мы перейдем к деталям двунаправленного поиска, давайте рассмотрим концепцию «шесть градусов разделения»
- В 1929 году венгерский автор Фригиса Каринти впервые предложил концепцию «шести градусов разлуки» в своих рассказах.
- Шесть градусов разделения - это идея, что все живые существа и все остальное в мире находятся в шести или менее шагах друг от друга.
Теперь давайте посмотрим на самую популярную социальную сеть, Facebook. Предположим, что обычный человек в Facebook имеет около 100 друзей. Тогда, если мы рассмотрим друзей друзей этого человека, это будет 100*100, которые составляют 10 000 друзей друзей. Если мы рассмотрим «друзья друзей друзей» , это будет в 100 раз больше или 1 миллион. И если мы продолжим это шесть раз, у нас будет 1Trillion People.
Но население мира составляет 7,6 миллиарда.
Теперь, как мы находим кратчайший путь между какими -либо двумя случайными лицами A и B через их соединения в социальной сети?
Давайте рассмотрим двунаправленный поиск. Итак, мы рассмотрим друзья друзей друзей и друзей друзей друзей Б., если концепция шести градусов разлуки верна, то среди друзей друзей друзей и друзей друзей Б.
Обратите внимание, что у нас будет около 1 миллиона друзей друзей как для A, так и B. Итак, в общей сложности мы рассмотрим только 2 миллиона человек в этом случае.
Алгоритм нормального Дейкстры должен был бы выглядеть примерно 2 миллиарда людей в социальной сети, чтобы найти самый короткий путь между A и B.
В этом мы проводим два одновременных поиска: один вперед от начального состояния и один назад от цели, останавливаясь, когда они встречаются в середине.
- Построить GR (обратный график)
- Начать Dijkstra из S (источник) в G и из T (Target) в Gr
- Чередование между шагами Dijkstra в G и в Gr
- Остановитесь, когда какая -то вершина «V» обрабатывается как в G, так и в Gr.
- Вычислить кратчайший путь между S и T.
Вычисление кратчайшего пути между S и T: Let Dist [u] - оценка расстояния в прямом диджстрах от S в G. Пусть диск [u] будет оценкой расстояния в обратной диджстрах от t в гр. После того, как какой -то узел «v» обрабатывается как в G, так и в Gr, какой -то кратчайший путь от S до T проходит через какой -то узел «U», который обрабатывается либо в G, в Gr или обоих и d (s, t) = dist [u] + диск [u]
