алгоритм Дейкстры - от А до Б

Question

Я знаю, что такое алгоритм Дейкстры.И я знаю, что это оптимально, когда используется для поиска всех путей от A до всех других возможных узлов.Однако оптимально ли это, если вы пытаетесь найти путь от А до Б?Другими словами, должен ли он использоваться при поиске пути от A до B или есть другие лучшие алгоритмы для этого варианта использования.

РЕДАКТИРОВАТЬ: Если я разорву цикл точно после того, как я нашел свой конечный узел, я думаю,что это не сработает.Допустим, у меня есть этот график https://i.stack.imgur.com/orp0N.png, и я пытаюсь перейти от A к D. Поскольку этот алгоритм жадный, он сначала пойдет A-> B, B-> F (тупик), B-> E, E-> D и общий вес будет 9. Хотя есть более короткий путь.Который будет найден в конце концов после этого пути.

Answer 1

Вам не нужно находить расстояние до ВСЕХ узлов от A. Вы просто выходите из цикла после помещения B в дерево кратчайшего пути.
Нет лучшего алгоритма с точки зрения производительности.Все алгоритмы, находящие кратчайший путь от конкретного узла, запускаются с O (n ^ 2) в худшем случае.

РЕДАКТИРОВАТЬ.Однако немного лучшей производительности можно достичь, если принять во внимание некоторые специфические особенности обработанного графа (например, соотношение количества вершин и ребер)

EDIT2.Относительно вашего примера графика.Вот шаги:
1. A добавлено к дереву кратчайшего пути (SPT)
2. Обновите его соседей, не входящих в SPT.dist (B) = 3
3. Выберите вершину с помощью min.dist.не в SPT.это B. добавьте B к SPT.
4. Обновите его соседей, не входящих в SPT.dist (C) = 6, dist (E) = 5, dist (F) = 4
5. Выберите вершину с помощью min.dist.не в SPT.это F. добавить F к SPT.
6. F не имеет соседей.
7. Выбрать вершину с помощью min.dist.не в SPT.это E. добавьте E к SPT.
8. Обновите его соседей, не входящих в SPT.dist (D) = 9
9. Выберите вершину с помощью min.dist.не в SPT.это C. добавьте C к SPT.
10. Обновите его соседей, не входящих в SPT.dist (D) = 7.
11. Выберите вершину с помощью min.dist.не в SPT.это D. добавить D к SPT.
Готово