Алгоритм Прима для взвешенного ориентированного графа

Я изучаю минимальное остовное дерево. Я просматриваю алгоритм Прима для взвешенного ориентированного графа.

Алгоритм простой

  • у вас есть два набора вершин: посещенные и непосещаемые
  • установить расстояние для всех краев до бесконечности
  • начать с любой вершины в непосещенном множестве и исследовать ее ребра
  • Во всех ребрах обновить расстояние до конечной вершины с весом ребра, если конечная вершина не посещена и если вес ребра меньше, чем расстояние до конечной вершины.
  • выберите непосещенную вершину с наименьшим расстоянием и сделайте это снова, пока не будут посещены все вершины

Я считаю, что с помощью вышеуказанного алгоритма я смогу найти остовное дерево с минимальной стоимостью среди всех остовных деревьев, то есть с минимальным остовным деревом.

Но я применил это к следующему примеру и считаю, что это не удалось.

Рассмотрим следующий пример

Вершинами являются {v1, v2, v3, v4, v5} и ребра с весом
(x, y): w =>
(v1, v2): 8
(v1, v3) : 15
(v1, v4): 7
(v2, v5): 4
(v4, v5): 7

Сначала я исследую v1, у него есть ребра к v2, v3, v4, поэтому граф становится
посещается вершина v1 и (вершина, расстояние) =>
(v2,8)
(v3,15 )
(v4,7)

Теперь v4 имеет наименьшее расстояние, т.е. 7, поэтому я исследую v4, он имеет край до v5, поэтому происходит следующая модификация
Посещается вершина v4 и ( вершина, расстояние) => (v5,7)

Теперь среди всех v5 наименьшее расстояние, то есть 7, поэтому я исследую v5, и у него нет края, поэтому я просто отмечаю его посещенным

Vertex v5 посещается

Теперь путаница начинается отсюда

Вершина с наименьшим расстоянием теперь v2, у нее есть ребро до v5 с весом 4, и в настоящее время v5 имеет расстояние 7, ранее назначенное ребром (v4, v5): 7, поэтому я считаю, что для создания минимального остовного дерева , расстояние для v5 должно быть обновлено с 7 до 4 как 4 ‹7, но этого не произойдет, потому что v5 уже был посещен, а алгоритм Прима не обновляет расстояние до вершины, которая уже была посещена, и расстояние для v5 останется 7 вместо 4 и у этого дерева не будет минимальной стоимости

Я правильно понял? или я ошибаюсь?

Спасибо


graph algorithm prims-algorithm minimum-spanning-tree
person Hassan    schedule 18.03.2014    source источник
comment
То, что вы описываете, на самом деле является алгоритмом Прима, но он работает только для неориентированных графов. Цитата из Википедии для ориентированной версии: Для ориентированных графов минимальное остовное дерево проблема называется проблемой Arborescence и может быть решена за квадратичное время с помощью < алгоритм href = "http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm" rel = "nofollow noreferrer"> Чу – Лю / Эдмондса.   -  person Gassa    schedule 18.03.2014
comment
это может быть даже решено за m + n log n, точно так же, как Prim   -  person Niklas B.    schedule 18.03.2014

Ответы (1)


arrow_upward
4
arrow_downward

Сначала я должен упомянуть, что алгоритм Прима применим только к неориентированным графам, поэтому, если мы считаем, что граф неориентированный, это шаг за шагом прогресс алгоритма в вашем случае:

введите описание изображения здесь

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

person mok    schedule 18.03.2014
comment
Но граф ОП направлен? - person Niklas B.; 18.03.2014
comment
@ NiklasB.- Алгоритм Прима для ориентированных графов ?! - person mok; 18.03.2014
comment
@NiklasB. Вы знаете, если мы рассматриваем ориентированные графы, это похоже на использование теоремы Пифагора для наклонного треугольника. - person mok; 18.03.2014
comment
Я знаю это, но OP, похоже, не знает. Возможно, вам следует указать, что это не работает для направленного случая, и предложить альтернативный алгоритм для случая, когда график действительно направлен - person Niklas B.; 18.03.2014
comment
@NiklasB. Хороший совет, я только что это сделал. - person mok; 18.03.2014