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

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

One Solution collect form web for “«Двунаправленная Dijkstra» от NetworkX”

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

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

Я буду основывать свое объяснение на вашем комментарии (на этот ответ )

Рассмотрим этот простой граф (с узлами 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) неверен.

Для справки, вот график: введите описание изображения здесь

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

Проблема заключается в непонимании того, что он делает до того, как он остановится. Он делает именно то, что вы ожидаете с точки зрения поиска узлов, но пока он делает это, есть дополнительная обработка, чтобы найти кратчайший путь. К тому времени, когда он достигнет 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 tot he cluster of E и проверим, находится ли какой-либо сосед C в кластере A Что ты знаешь, есть A Итак, у нас есть кандидат кратчайшего пути ACE, с расстоянием 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: ACE, length 7 

Назад к A : Мы получаем следующую вещь из ее бахромы, D Мы добавим его в кластер вокруг A и заметим, что его сосед C находится в кластере около E Итак, у нас есть новый путь кандидата, ADCE , но длина больше 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: ACE, length 7 

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

  • Исправить положение подмножества узлов в весовом графике NetworkX
  • Как создать графики сети Gephi из Python?
  • Networkx: перекрытие краев при визуализации MultiGraph
  • NetworkX - Как представить грани, связанные с пути
  • Как я могу получить количество узлов базы данных диаграммы Neo4j из Python?
  • Рисование графика с помощью NetworkX на базовой карте
  • networkx add_node с определенной позицией
  • Можно ли получить иерархические графики из networkx с помощью python 3?
  • Python - лучший язык программирования в мире.