В чем разница между алгоритмом Дейкстры и Прима?

Может ли кто-нибудь сказать мне разницу между алгоритмами Dijkstra и Prim's? Я знаю, что делают каждый из алгоритмов. Но они выглядят одинаково для меня. Алгоритм Дейкстры хранит суммирование минимумов минимальной стоимости, тогда как алгоритм Prim хранит не более одного минимального края затрат. Разве это не так?

Ответ 1

Алгоритм Dijsktra находит минимальное расстояние от node я до всех узлов (вы указываете i). Поэтому взамен вы получаете дерево минимального расстояния от node i.

Алгоритм Примм дает вам минимальное связующее дерево для заданного графа. Дерево, которое соединяет все узлы, в то время как сумма всех затрат минимальна.

Итак, с Dijkstra вы можете перейти от выбранного node к любому другому с минимальной стоимостью, вы не получите это с помощью Prim

Ответ 2

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

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

Простыми словами:

Итак, если вы хотите развернуть поезд для соединения нескольких городов, вы должны использовать Prim algo. Но если вы хотите переехать из одного города в другое сбережение как можно больше времени, вы должны использовать Dijkstra algo.

Ответ 3

Оба могут быть реализованы с использованием точно такого же общего алгоритма:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Для Prim, pass f = w(u, v) и для Dijkstra pass f = u.key + w(u, v).

Еще одна интересная вещь: выше Generic может также реализовать Breadth First Search (BFS), хотя это будет излишним, потому что дорогостоящая очередь приоритетов не требуется. Чтобы включить выше общий алгоритм в BFS, пройдите f = u.key + 1, который будет таким же, как и принудительное выполнение всех весов до 1 (то есть BFS дает минимальное количество ребер, необходимых для перехода от точки A к B).

Интуиция

Вот один хороший способ подумать об общем алгоритме: мы начинаем с двух ведер A и B. Сначала положите все ваши вершины в B, чтобы ведро A было пустым. Затем мы переместим одну вершину из B в A. Теперь посмотрим на все ребра из вершин в A, пересекающихся с вершинами в B. Мы выбрали одно ребро, используя некоторые критерии из этих кросс-ребер, и переместим соответствующую вершину из B в A. Повторите этот процесс до тех пор, пока B не станет пустым.

Скорее всего, для реализации этой идеи будет поддерживать приоритетную очередь ребер для вершин в A, пересекающихся с B. Очевидно, что это было бы неприятно, если бы график был не разреженным. Таким образом, вопрос может заключаться в том, что мы можем поддерживать очередь приоритетов вершин? На самом деле мы можем, так как наше решение, наконец, состоит в том, какую вершину выбрать из B.

Исторический контекст

Интересно, что общая версия методики, лежащей в основе обоих алгоритмов, концептуально стареет до 1930 года, даже когда электронных компьютеров не было.

История начинается с Отакара Боревки, которому нужен алгоритм для друга семьи, пытающегося выяснить, как подключить города в стране Моравия (теперь часть Чехии) с минимальными затратами электрических линий. Он опубликовал свой алгоритм в 1926 году в журнале, посвящённом математике, поскольку тогда Computer Science не существовала. Это обратило внимание на Войтеча Ярника, который подумал об улучшении алгоритма Borůvka и опубликовал его в 1930 году. Фактически он обнаружил тот же алгоритм, который мы теперь знаем как алгоритм Prim, который вновь открыл его в 1957 году.

Независимо от всего этого, в 1956 году Дейкстре нужно было написать программу, чтобы продемонстрировать возможности нового компьютера, разработанного его институтом. Он подумал, что было бы здорово, если бы компьютер нашел связь между двумя городами Нидерландов. Он разработал алгоритм за 20 минут. Он создал график из 64 городов с некоторыми упрощениями (потому что его компьютер был 6-бит) и написал код для этого компьютера 1956 года. Однако он не опубликовал свой алгоритм, потому что в основном не было журналов для компьютерных наук, и он думал, что это может быть не очень важно. В следующем году он узнал о проблеме подключения терминалов новых компьютеров, так что длина проводов была минимизирована. Он подумал об этой проблеме и вновь открыл алгоритм Jarník/Prim, который снова использует ту же технику, что и алгоритм кратчайшего пути, который он обнаружил год назад. Он отметил, что оба его алгоритма были разработаны без использования ручки или бумаги. В 1959 году он опубликовал оба алгоритма в документе который составляет всего 2 с половиной страницы.

Ответ 4

Алгоритм Дийкстра - это проблема кратчайшего пути с одним источником между node я и j, но алгоритм Prim - минимальная проблема связующего дерева. Этот алгоритм использует концепцию программирования под названием "жадный алгоритм"

Если вы проверите это понятие, посетите

Замечание лексического алгоритма: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/07-greedy.pdf
Минимальное остовное дерево: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/18-mst.pdf
Самый короткий путь для одного источника: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/19-sssp.pdf

Ответ 5

В последнее время меня беспокоил тот же вопрос, и я думаю, что могу поделиться своим пониманием...

Я думаю, что ключевое различие между этими двумя алгоритмами (Dijkstra и Prim) корнями в проблеме, которую они предназначены для решения, а именно, кратчайший путь между двумя узлами и минимальным остовным деревом (MST). Формально найти кратчайший путь между словами: node s и t, а рациональным требованием является посещение каждого края графика не более одного раза. Однако он НЕ требует, чтобы мы посетили все node. Последний (MST) должен заставить нас посетить ВСЕ node (не чаще одного раза) и с тем же рациональным требованием посещать каждое ребро не более одного раза.

Сказав это, Дейкстра позволяет нам "делать ярлык" так долго, что я могу получить от s до t, не беспокоясь о последствиях - как только я доберусь до t, я закончил! Хотя в MST есть путь от s до t, но этот путь s-t создается с учетом всех остальных узлов, поэтому этот путь может быть длиннее пути s-t, найденного алгоритмом Дийстры. Ниже приведен краткий пример с тремя узлами:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Предположим, что каждый из верхних ребер имеет стоимость 2, а нижний край имеет стоимость 3, тогда Дийктра скажет нам, что мы берем нижний путь, так как мы не заботимся о середине node. С другой стороны, Prim вернет нам MST с двумя верхними краями, отбрасывая нижний край.

Такое различие также отражается на тонкой разнице в реализациях: в алгоритме Дейкстры нужно иметь этап сохранения книги (для каждого node) для обновления кратчайшего пути из s после поглощения нового node, тогда как в алгоритме Prim нет такой необходимости.