«Двунаправленная Dijkstra» от NetworkX

Question

Я только что прочитал реализацию NetworkX алгоритма Дейкстры для кратчайших путей с использованием двунаправленного поиска (по адресу this). Какова точка завершения этого метода?

Answer 1

Я собираюсь основывать это на реализации networkx.

Двунаправленный Dijkstra останавливается, когда он встречает один и тот же узел в обоих направлениях, но путь, который он возвращает в этой точке, может быть не через этот узел. Он выполняет дополнительные вычисления для отслеживания лучшего кандидата для кратчайшего пути.

Я собираюсь основывать свои объяснения на ваш комментарий (на this answer)

Рассмотрим простой граф (с узлами A, B, C, D, E). Края этого графика и их веса: «A-> B: 1», «A-> C: 6", "A-> D: 4", "A-> E: 10", "D-> С: 3" , "С-> Е: 1". когда я использую алгоритм Дейкстры для этого графа с обеих сторон: вперёд он находит B после A, а затем D, в обратном - находит C после E, а затем D. в этой точке оба набора имеют одну и ту же вершину и пересечение. Это точка окончания или она должна быть продолжена? потому что этот ответ (A-> D-> C-> E) неверен.

Для справки, вот график:

Когда я бег двунаправленной Алгоритм Дейкстров NetworkX в на (неориентированных) сети в контрпримере вы утверждали, что комментарий: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1": это дает мне: (7, ['A', 'C', 'E']), не A-D-C-E.

Проблема заключается в непонимании того, что она делает до останавливается. Он делает именно то, что вы ожидаете с точки зрения поиска узлов, но пока он делает это, есть дополнительная обработка, чтобы найти кратчайший путь. К тому времени, когда он достигнет D с обоих направлений, он уже собрал несколько других «возможных» путей, которые могут быть короче. Нет никакой гарантии, что только потому, что узел D достигнут с обоих концов, что заканчивается тем, что является частью кратчайшего пути. Скорее, в точке, где узел был достигнут с обоих направлений, текущий самый короткий путь кандидата короче любых возможных путей, которые он найдет, если он продолжит работу.

Алгоритм начинается с двух пустых кластеров, каждый из которых связан с A или E

{}   {} 

и он будет строить «кластеры» вокруг каждого из них. Это первая ставит A в кластер, связанный с A

{A:0}   {} 

Теперь он проверяет A уже в кластере около E (который в настоящее время пуст). Это не. Затем он смотрит на каждого соседа A и проверяет, находятся ли они в кластере около E. Они не. Затем он помещает всех этих соседей в кучу (например, упорядоченный список) соседних соседей A, упорядоченных по длине пути от A. Назовем это 'бахрома' из A

clusters     .....  fringes 

{A:0}   {}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[] 

Теперь он проверяет E. Для E это делает симметричную вещь. Поместите E в свой кластер. Убедитесь, что E нет в списке вокруг A.Затем проверьте все его соседи, чтобы узнать, есть ли в кластере около A (они не являются). Затем создается бахрома E.

clusters         fringes 
{A:0}   {E:0}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

Теперь оно возвращается к A. Он принимает B из списка и добавляет его в кластер около A. Он проверяет, находится ли какой-либо сосед из B в кластере около E (соседи не рассматривают). Итак, мы имеем:

clusters         fringes 
{A:0, B:1}  {E:0}  .....  A:[(D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

Назад к E: добавить C карапуз он кластер из E и проверить, является ли какой-нибудь сосед C в кластере A. Что вы знаете, есть A. Итак, у нас есть кандидат кратчайший путь A-C-E, с расстоянием 7. Мы будем придерживаться этого. Добавим D, чтобы добавить к бахромой E (с расстоянием 4, так как это 1 + 3). Мы имеем:

clusters         fringes 
{A:0, B:1}  {E:0, C:1}  ..... A:[(D,4), (C,6), (E,10)] 
             E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

Вернуться к A: Мы получаем следующую вещь из его бахромы, D. Мы добавим его в кластер около A и отметим, что его сосед C находится в кластере около E. Итак, у нас есть новый путь кандидата, A-D-C-E, но длина больше 7, поэтому мы отбрасываем его.

clusters         fringes 
{A:0, B:1, D:4}  {E:0, C:1}  ..... A:[(C,6), (E,10)] 
              E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

Теперь мы возвращаемся к E. Мы смотрим на D. Он находится в кластере около A. Мы можем быть уверены, что любой будущий путь кандидата, с которым мы столкнулись, будет иметь длину, по крайней мере, такую ​​же длину, как и путь A-D-C-E, который мы только что проследили (это утверждение не обязательно очевидно, но это ключ к этому подходу). Поэтому мы можем остановиться. Мы возвращаем путь кандидата, найденный ранее.