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

Алгоритм Дейкстры не создает MST, он находит кратчайший путь.

Рассмотрим этот график

       5     5
  s *-----*-----* t
     \         /
       -------
         9

Кратчайший путь - 9, в то время как MST - это другой «путь» на 10.

Алгоритмы Прима и Дейкстры почти одинаковы, за исключением «функции релаксации».

Прим:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Дейкстра:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Единственное различие указано стрелкой, которая является функцией релаксации.

• Prim, который ищет минимальное остовное дерево, заботится только о минимуме из общего числа ребер, покрывающих все вершины. Функция релаксации alt = w(u,v)
• Dijkstra, который ищет минимальную длину пути, поэтому он заботится о накоплении ребер. Функция релаксации alt = w(u,v) + u.key

Алгоритм Дийсктры находит минимальное расстояние от узла i до всех узлов (вы указываете i). Итак, взамен вы получаете дерево минимального расстояния от узла i.

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

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

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

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

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

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

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

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

Для Прим пройти f = w(u, v), а для Дейкстры пройти f = u.key + w(u, v).

Еще одна интересная вещь заключается в том, что вышеупомянутый Generic также может реализовать поиск в ширину (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 году в журнале, посвященном математике, поскольку компьютерных наук тогда не существовало. Это привлекло внимание Войтеха Ярника, который подумал об улучшении алгоритма Борувки и опубликовал его в 1930 году. Он фактически открыл тот же алгоритм, который мы теперь знаем как алгоритм Прима, который повторно открыл его в 1957 году.

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

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

Алгоритм Prims дает вам MST для данного графа, то есть дерева, которое соединяет все узлы, в то время как сумма всех затрат является минимально возможной.

Короче говоря, на реалистичном примере:

1. Дейкстра хочет узнать кратчайший путь к каждой точке назначения, сэкономив время в пути и топливо.
2. Прим хочет знать, как эффективно развернуть железнодорожную систему, т.е. сэкономить на материальных затратах.

Непосредственно из статьи в Википедии алгоритма Дейкстры:

Процесс, лежащий в основе алгоритма Дейкстры, похож на жадный процесс, используемый в алгоритме Прима. Цель Prim - найти минимальное остовное дерево, которое соединяет все узлы в графе; Дейкстра имеет дело только с двумя узлами. Prim не оценивает общий вес пути от начального узла, только отдельный путь.

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

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

При этом Дейкстра позволяет нам «сокращаться» так долго, что я могу добраться от s до t, не беспокоясь о последствиях - как только я доберусь до t < / em>, готово! Хотя в MST также есть путь от s к t, но этот путь s - t создается с учетом всех остальных узлов, поэтому этот путь может быть длиннее, чем путь s - t, найденный алгоритмом Дийстры. Ниже приведен быстрый пример с 3 узлами:

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