Когда алгоритм Дейкстры и алгоритм Прима производят разные выходы?

Question

Я знаю разницу между алгоритмом Прима и Дейкстры. Первый создает MST, а последний дает кратчайший путь от источника ко всему узлу. Математически это не одно и то же, поэтому мы не ожидаем, что оба алгоритма будут давать одинаковые результаты.

Однако, пробуя разные примеры, я получаю тот же результат. Псевдокод для алгоритма Прима и алгоритма Дейкстры также очень похожи. Может кто-нибудь, пожалуйста, дайте мне пример, где Prim приносит MST, который не будет получен при решении с помощью Дийкстры или наоборот.

Также, согласно моим знаниям. Оба алгоритма используют следующий подход. Пожалуйста, поправьте меня, если я ошибаюсь:

Найти кратчайшее I-J, где я из множества, которая уже была включена и J из множества, которые не были включены еще и затем добавить J к набору.

Answer 1

Простым примером является сборник из четырех узлов, расположенных по углам квадрата. Поместите края стоимости 2 между любыми двумя соседними углами и поместите края цены 3, идущие по диагонали по площади. Запуск алгоритма Дейкстры из любого уголка подберут эти края:

* -- * 
| \ 
| \ 
* * 

Это кратчайшие пути, а общая стоимость ребер 7.

Запуск алгоритма Прима подберут эти края:

* -- * 
| 
| 
* -- * 

Это MST (общая стоимость края 6), но это не кратчайшие пути (путь от верхнего левого угла до нижнего правого угла имеет стоимость 4, но возможен более прямой маршрут).

Как вызов: попытаться найти графики, где

• алгоритм Дейкстры находит дерево кратчайшего пути, который Ω (п) раз тяжелее, чем фактическая MST и
• алгоритм Прима находит MST где пути в дерево равно Ω (n) раз дольше, чем в соответствующем дереве кратчайшего пути.

Prim и Dijkstra выбирают узел, находя какой-то узел не в наборе и внося его в набор, но они отличаются тем, как они регулируют расстояния. В алгоритме Prim, используемые расстояния всегда являются минимальным расстоянием от любого узла из набора до любого узла внутри набора. В алгоритме Дейкстры, расстояние минимум следующее значение:

расстояние (начальный узел, и) + L (U, V)

Другими словами, коэффициенты алгоритма Дейкстры на расстоянии от начального узла до узлов вне набора, в то время как Prim's - нет.

Надеюсь, это поможет!

Answer 2

Рассмотрите, что a-b имеет длину 100 и a-c имеет длину 100 и b-c имеет 1 длину. Самое короткое дерево путей, укорененное в a, является a-b и a-c. Mst - b-c и один из других ребер. Ссылка: Create a MST with depth-first search?.