В чем разница между алгоритмом Дейкстры и Прима?
Кто-нибудь может сказать мне разницу между алгоритмами Дейкстры и Прима? Я знаю, что делает каждый из алгоритмов. Но они выглядят одинаково для меня. Алгоритм Дейкстры хранит суммирование ребер минимальной стоимости, тогда как алгоритм Прима хранит не более одного ребра минимальной стоимости. Разве это не то же самое?
6 ответов
Алгоритм Дийсктра находит минимальное расстояние от узла i до всех узлов (вы указываете i). Таким образом, взамен вы получаете дерево минимального расстояния от узла i.
Алгоритм простых чисел дает вам минимальное остовное дерево для данного графа. Дерево, которое соединяет все узлы, а сумма всех затрат является минимально возможной.
Таким образом, с Dijkstra вы можете перейти от выбранного узла к любому другому с минимальной стоимостью, вы не получите это с Prim's
Единственное отличие, которое я вижу, состоит в том, что алгоритм Прима хранит минимальное ребро стоимости, тогда как алгоритм Дейкстры хранит общую стоимость от исходной вершины до текущей вершины.
Dijkstra дает вам путь от исходного узла до конечного узла, так что стоимость минимальна. Однако алгоритм Prim дает вам минимальное связующее дерево, так что все узлы соединены, а общая стоимость минимальна.
Простыми словами:
Итак, если вы хотите развернуть поезд, чтобы соединить несколько городов, вы должны использовать алгоритм Прима. Но если вы хотите поехать из одного города в другой, сэкономив как можно больше времени, вы бы использовали алгоритм Дейкстры.
Оба могут быть реализованы с использованием точно такого же общего алгоритма, как показано ниже:
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) и для Dijkstra Pass f = u.key + w(u, v),
Еще одна интересная вещь заключается в том, что выше Generic также может реализовывать поиск в ширину (BFS), хотя это было бы излишним, потому что дорогая очередь с приоритетами не требуется. Чтобы превратить вышеупомянутый общий алгоритм в BFS, передайте f = u.key + 1 что аналогично приведению всех весов в 1 (т. е. BFS дает минимальное количество ребер, необходимое для перемещения из точки А в В).
Интуиция
Вот один хороший способ подумать о вышеупомянутом обобщенном алгоритме: мы начнем с двух сегментов A и B. Сначала поместите все ваши вершины в B, чтобы бак A был пустым. Затем мы перемещаем одну вершину из B в A. Теперь рассмотрим все ребра из вершин в A, которые пересекаются с вершинами из B. Мы выбрали одно ребро, используя некоторые критерии из этих пересекающихся ребер, и переместим соответствующую вершину из B в A. Повторяйте этот процесс, пока B не станет пустым.
Грубым способом реализации этой идеи было бы сохранение приоритетной очереди ребер для вершин в A, которые пересекаются с B. Очевидно, это было бы проблематично, если бы граф не был разреженным. Поэтому вопрос заключается в том, можем ли мы вместо этого поддерживать приоритетную очередь вершин? Это на самом деле мы можем в качестве нашего решения, наконец, какую вершину выбрать из B.
Исторический контекст
Интересно, что общая версия технологии, лежащей в основе обоих алгоритмов, концептуально устарела в 1930 году, даже когда не было электронных компьютеров.
История начинается с Отакара Боровки, который нуждался в алгоритме для друга семьи, пытающегося выяснить, как соединить города в стране Моравия (теперь часть Чешской Республики) с минимальными затратами линий электропередач. Он опубликовал свой алгоритм в 1926 году в журнале по математике, так как компьютерных наук тогда не существовало. Это привлекло внимание Войтеша Ярника, который подумал об улучшении алгоритма Боровки и опубликовал его в 1930 году. Он фактически обнаружил тот же алгоритм, который мы теперь знаем, как алгоритм Прима, который вновь открыл его в 1957 году.
Независимо от всего этого, в 1956 году Дейкстра должен был написать программу для демонстрации возможностей нового компьютера, разработанного его институтом. Он подумал, что было бы здорово, чтобы компьютер нашел связь между двумя городами Нидерландов. Он разработал алгоритм за 20 минут. Он создал график из 64 городов с некоторыми упрощениями (потому что его компьютер был 6-разрядным) и написал код для этого компьютера 1956 года. Однако он не опубликовал свой алгоритм, потому что в основном не было журналов по информатике, и он думал, что это может быть не очень важно. В следующем году он узнал о проблеме подключения терминалов новых компьютеров таким образом, чтобы длина проводов была минимизирована. Он подумал об этой проблеме и заново открыл алгоритм Ярника / Прима, который снова использует ту же технику, что и алгоритм кратчайшего пути, который он открыл годом ранее. Он упомянул, что оба его алгоритма были разработаны без использования ручки или бумаги. В 1959 году он опубликовал оба алгоритма в статье длиной всего 2 с половиной страницы.
В последнее время меня беспокоил тот же вопрос, и я думаю, что могу поделиться своим пониманием...
Я думаю, что ключевое различие между этими двумя алгоритмами (Dijkstra и Prim) коренится в проблеме, для решения которой они предназначены, а именно в кратчайшем пути между двумя узлами и минимальном остовном дереве (MST). Формально это найти кратчайший путь, скажем, между узлами s и t, а рациональное требование - посещать каждый край графа не более одного раза. Тем не менее, это не требует от нас посещения всех узлов. Последнее (MST) - это заставить нас посетить ВСЕ узел (не более одного раза), и с тем же рациональным требованием посещения каждого ребра не более одного раза.
При этом Дейкстра позволяет нам "сокращать путь" так долго, что я могу переходить от s к t, не беспокоясь о последствиях - как только я доберусь до t, все готово! Хотя в MST также есть путь от s до t, но этот путь s - t создается с учетом всех остальных узлов, поэтому этот путь может быть длиннее, чем путь s - t, найденный алгоритмом Диджстры. Ниже приведен краткий пример с 3 узлами:
2 2
(s) o ----- o ----- o (t)
| |
-----------------
3
Допустим, каждый из верхних ребер имеет стоимость 2, а нижний ребро имеет стоимость 3, тогда Дийктра скажет нам взять нижний путь, так как нас не волнует средний узел. С другой стороны, Prim вернет нам MST с двумя верхними краями, отбрасывая нижний край.
Такое различие также отражено в тонкой разнице в реализациях: в алгоритме Дейкстры необходимо иметь шаг бухгалтерского учета (для каждого узла), чтобы обновить кратчайший путь из s после поглощения нового узла, тогда как в алгоритме Прима есть нет такой необходимости.
Самое простое объяснение в Prims: вы не указываете начальный узел, но в dijsktra вам (необходимо иметь начальный узел) нужно найти кратчайший путь от данного узла ко всем остальным узлам.
Алгоритм Дейкстры - это проблема кратчайшего пути из одного источника между узлами i и j, но алгоритм Прима - минимальная проблема связующего дерева. Эти алгоритмы используют концепцию программирования под названием "жадный алгоритм"
Если вы проверите эти понятия, пожалуйста, посетите
- Лекция по жадному алгоритму: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
- Минимальное связующее дерево: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
- Кратчайший путь из одного источника: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf