Разница между алгоритмами Прима и Дейкстры?
В чем точная разница между алгоритмами Дейкстры и Прима? Я знаю, что Prim даст MST, но дерево, сгенерированное Dijkstra, также будет MST. Тогда какая точная разница?
13 ответов
Алгоритм Прима создает минимальное остовное дерево для графа, которое представляет собой дерево, которое соединяет все узлы графа и имеет наименьшую общую стоимость среди всех деревьев, которые соединяют все узлы. Однако длина пути между любыми двумя узлами в MST может не быть кратчайшим путем между этими двумя узлами в исходном графе. MST полезны, например, если вы хотите физически подключить узлы на графике, чтобы обеспечить их электроэнергией с наименьшей общей стоимостью. Неважно, что длина пути между двумя узлами может быть неоптимальной, так как все, что вас волнует, это тот факт, что они связаны.
Алгоритм Дейкстры строит дерево кратчайших путей, начиная с некоторого исходного узла. Дерево кратчайшего пути - это дерево, которое соединяет все узлы в графе обратно с узлом-источником и обладает свойством минимизации длины любого пути от узла-источника до любого другого узла в графе. Это полезно, например, если вы хотите построить дорожную сеть, которая позволила бы каждому как можно более эффективно добраться до какого-либо важного ориентира. Однако не гарантируется, что дерево с кратчайшим путем является минимальным остовным деревом, и стоимость создания такого дерева может быть намного больше, чем стоимость MST.
Другое важное различие касается графиков, над которыми работают алгоритмы. Алгоритм Прима работает только с неориентированными графами, поскольку концепция MST предполагает, что графы по своей природе не являются ненаправленными. (Для ориентированных графов есть нечто, называемое "минимальной остаточной древовидностью", но алгоритмы их поиска намного сложнее). Алгоритм Дейкстры будет отлично работать на ориентированных графах, поскольку деревья кратчайших путей действительно могут быть направлены. Кроме того, алгоритм Дейкстры не обязательно дает правильное решение в графах, содержащих отрицательные веса ребер, в то время как алгоритм Прима может справиться с этим.
Надеюсь это поможет!
Алгоритм Дейкстры не создает 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) and w(u,v) < v.key
v.parent = u
v.key = w(u,v) <== relax function, Pay attention here
}
В Дейкстре:
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) and w(u,v) < v.key
v.parent = u
v.key = w(u,v) + u.key <== relax function, Pay attention here
}
Единственное отличие - последняя строка кода, которая является функцией релакс. Prim, который ищет минимальное остовное дерево, заботится только о минимуме всех ребер, покрывающих все вершины. так это выглядит так: v.key = w(u,v) Dijkstra, который ищет минимальную длину пути, поэтому он заботится о накоплении ребер. Так это выглядит так:v.key = w(u,v) + u.key
Дейкстра находит кратчайший путь между своим начальным узлом и каждым другим узлом. Таким образом, взамен вы получаете дерево минимального расстояния от начального узла, т.е. вы можете достичь любого другого узла настолько эффективно, насколько это возможно.
Алгоритм Prims дает вам MST для данного графа, то есть дерева, которое соединяет все узлы, а сумма всех затрат является минимально возможной.
Чтобы сделать историю короткой с реалистичным примером:
- Дейкстра хочет знать кратчайший путь к каждому пункту назначения, экономя время в пути и топливо.
- Prim хочет знать, как эффективно развернуть железнодорожную железнодорожную систему, т.е. сэкономить материальные затраты.
Вот что мне понравилось: подумайте, какую вершину алгоритм займет следующей:
Алгоритм Прима берет следующую вершину, ближайшую к дереву , то есть самую близкую к какой-либо вершине в любом месте дерева .
Алгоритм Дейкстры берет следующую вершину, ближайшую к источнику.
Источник: лекция Р. Седжвика об алгоритме Дейкстры, Алгоритмы, часть II: https://coursera.org/share/a551af98e24292b6445c82a2a5f16b18
Непосредственно из статьи Википедии Алгоритма Дейкстры:
Процесс, лежащий в основе алгоритма Дейкстры, похож на жадный процесс, используемый в алгоритме Прима. Цель Прима - найти минимальное остовное дерево, которое соединяет все узлы в графе; Дейкстра имеет дело только с двумя узлами. Prim's не оценивает общий вес пути от начального узла, а только отдельный путь.
Алгоритм Дейкстры используется только для поиска кратчайшего пути.
В Minimum Spanning tree(алгоритм Прима или Крускала) вы получаете минимальные egdes с минимальным значением ребра.
Например:- Рассмотрим ситуацию, когда вы не хотите создавать огромную сеть, для которой вам потребуется большое количество проводов, поэтому подсчет проводов можно выполнить с помощью Minimum Spanning Tree(алгоритм Прима или Крускала) (т.е. дать вам минимальное количество проводов для создания огромного проводного сетевого соединения с минимальными затратами).
Принимая во внимание, что "алгоритм Dijkstras" будет использоваться для получения кратчайшего пути между двумя узлами при соединении любых узлов друг с другом.
Ключевое различие между основными алгоритмами заключается в их различных критериях выбора ребер. Как правило, они оба используют приоритетную очередь для выбора следующих узлов, но имеют разные критерии для выбора соседних узлов текущих узлов обработки: алгоритм Прима требует, чтобы следующие соседние узлы также были сохранены в очереди, в то время как алгоритм Дейкстры не делает:
def dijkstra(g, s):
q <- make_priority_queue(VERTEX.distance)
for each vertex v in g.vertex:
v.distance <- infinite
v.predecessor ~> nil
q.add(v)
s.distance <- 0
while not q.is_empty:
u <- q.extract_min()
for each adjacent vertex v of u:
...
def prim(g, s):
q <- make_priority_queue(VERTEX.distance)
for each vertex v in g.vertex:
v.distance <- infinite
v.predecessor ~> nil
q.add(v)
s.distance <- 0
while not q.is_empty:
u <- q.extract_min()
for each adjacent vertex v of u:
if v in q and weight(u, v) < v.distance:// <-------selection--------
...
Расчеты vertex.distance являются второй другой точкой.
На уровне кода другое отличие - это API.
Вы инициализируете Prim исходной вершиной s, т.е. Prim.new(s); s может быть любой вершиной, и независимо от s конечный результат, который является ребрами минимального остовного дерева (MST), одинаков. Чтобы получить ребра MST, мы вызываем метод edges(),
Вы инициализируете Dijkstra с исходной вершиной s, т.е. Dijkstra.new(s) что вы хотите получить кратчайший путь / расстояние до всех других вершин. Конечные результаты, которые являются кратчайшим путем / расстоянием от s до всех других вершин; разные в зависимости от с. Чтобы получить кратчайшие пути / расстояния от s до любой вершины v, мы вызываем методы distanceTo(v) а также pathTo(v) соответственно.
Первое отличие состоит в том, что алгоритм Дейкстры решает другую проблему, нежели Крускал и Прим. Дейкстра решает проблему кратчайшего пути (из указанного узла), а Крускал и Прим находят остовное дерево с минимальной стоимостью. Ниже приведена модифицированная форма описания, которое я написал на этой странице: Графовые алгоритмы.
Для любого графа остовное дерево - это набор ребер, достаточный для обеспечения ровно одного пути между каждой парой вершин. Это ограничение означает, что не может быть цепей, образованных выбранными ребрами.
Покрывающее дерево с минимальной стоимостью - это дерево с наименьшим возможным общим весом (где вес представляет собой стоимость или расстояние). Таких деревьев может быть больше одного, но Прим и Крускал гарантированно найдут одно из них.
Для указанной вершины (скажем, X) дерево кратчайшего пути является остовным деревом, так что путь от X до любой другой вершины максимально короткий (т. Е. Имеет минимально возможный вес).
Прим и Дейкстра "вырастают" дерево из начальной вершины. Другими словами, они имеют "локальную" направленность; на каждом шаге мы рассматриваем только те ребра, которые примыкают к ранее выбранным вершинам, выбирая самый дешевый вариант, который удовлетворяет нашим потребностям. Между тем, Kruskal является "глобальным" алгоритмом, означающим, что каждое ребро (жадно) выбирается из всего графа. (На самом деле, Дейкстра может рассматриваться как имеющий некоторый глобальный аспект, как отмечено ниже.)
Чтобы найти связующее дерево с минимальной стоимостью:
Крускал (глобальный подход): На каждом шаге выбирайте самый дешевый доступный край в любом месте, который не нарушает цель создания связующего дерева. Prim (локальный подход): выберите начальную вершину. На каждом последующем шаге выбирайте самый дешевый доступный край, присоединенный к любой ранее выбранной вершине, которая не нарушает цель создания связующего дерева. Чтобы найти остовное дерево кратчайшего пути:
Dijkstra: на каждом шаге выберите ребро, прикрепленное к любой ранее выбранной вершине (локальный аспект), которое делает общее расстояние от начальной вершины (глобальный аспект) как можно меньшим, и не нарушает цель создания остовного дерева,
Деревья минимальной стоимости и деревья кратчайшего пути легко перепутать, как и алгоритмы Прима и Дейкстры, которые их решают. Оба алгоритма "вырастают" из начальной вершины, на каждом шаге выбирая ребро, которое соединяет вершину Y, которая находится в дереве, с вершиной Z, которой нет. Однако, в то время как Prim выбирает самое дешевое такое ребро, Dijkstra выбирает ребро, что приводит к кратчайшему пути от X до Z.
Простая иллюстрация помогает понять разницу между этими алгоритмами и деревьями, которые они создают. На приведенном ниже графике, начиная с вершины A, Prim и Dijkstra начинаются с выбора ребра AB, а затем добавления ребра BD. Здесь два алгоритма расходятся: Prim завершает дерево, добавляя ребро DC, а Dijkstra добавляет AC или BC, потому что пути AC и ABC (оба с общим расстоянием 30) короче, чем путь ABDC (общее расстояние 31).
Они оба создают деревья жадным методом.
С помощью алгоритма Прима мы находим остовное дерево минимальной стоимости. Цель состоит в том, чтобы найти минимальную стоимость для покрытия всех узлов.
с Дейкстрой мы находим кратчайший путь из одного источника. Цель состоит в том, чтобы найти кратчайший путь от источника к любому другому узлу.
Алгоритм Прима работает точно так же, как алгоритм Дейкстры, за исключением
- Он не отслеживает расстояние от источника.
- Сохранение ребра, соединяющего переднюю часть посещенных вершин со следующей ближайшей вершиной.
- Вершина, используемая в качестве «источника» для алгоритма Прима, будет корнем MST.
@templatetypedef покрыл разницу между MST и кратчайшим путем. Я рассмотрел разницу алгоритма в другом ответе, продемонстрировав, что оба могут быть реализованы с использованием одного и того же универсального алгоритма, который принимает еще один параметр в качестве входных данных: функция f(u,v), Разница между алгоритмом Прима и Дейкстры состоит в том, что f(u,v) ты используешь.
У Дейкстры и Прима есть одна общая черта: они оба начинают с одного узла, и им обоим приходится выбирать узел в каждом цикле. Для Дейкстры выбранный узел имеет наименьшее значение в массиве dist[]; в то время как для Prim выбранный узел примыкает к ребру, имеющему наименьший вес.
В большинстве случаев узел, который они выбирают в каждом цикле, различен. Например, для этого графика:
*D
|
|4
|
5 | 5
A*-----*B-----*C
\__________/
8
Начиная с узла A, Прим и Дейкстра затем выберут узел B. Но затем Прим выберет узел D, а Дейкстра вместо этого выберет узел C.