Что такое минимальное остовное дерево Дейкстры?

avatar
Marcus Kim
8 апреля 2018 в 07:17
1190
1
4

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

Для каждого ребра добавьте его в дерево. Если обнаружен цикл, удалите самый тяжелый край.

Я облазил Интернет и не смог найти алгоритм для этого.

Возможно, мне нужно просто написать код для себя, но я решил спросить, есть ли у кого-нибудь хороший пример.

Кто-нибудь может помочь?

Источник
StoryTeller - Unslander Monica
8 апреля 2018 в 07:19
2

Вероятно, потому, что он более известен как Алгоритм Прима.

user202729
8 апреля 2018 в 07:21
0

@StoryTeller Нет, я так не думаю. В частности, я не знаю ни одного алгоритма, который удаляет ребра — ни Крускал, ни Прим (алгоритм ) этого не делают.

StoryTeller - Unslander Monica
8 апреля 2018 в 07:24
1

@user202729 user202729 - Ну, я знаю только один алгоритм поиска MST, который приписывается Дейкстре. В любом случае материал класса OP кажется неточным.

Jochen Schwarze
8 апреля 2018 в 08:04
0

Это также известно как проблема дерева Штейнера? Если да, то загляните на grass.osgeo.org/grass70/manuals/v.net.steiner.html, я думаю, что найти исходники тоже не проблема.

Ian4264
8 апреля 2018 в 08:11
0

Может ли это быть алгоритм обратного удаления en.m.wikipedia.org/wiki/Reverse-delete_algorithm?

rustyx
8 апреля 2018 в 08:12
0

Такого нет. Дейкстры — алгоритм поиска кратчайшего пути.

molbdnilo
8 апреля 2018 в 08:23
0

Есть два популярных алгоритма MST: Крускала и Прима. Нет и того, что вы описали. Существует вариант кратчайшего пути Дейкстры, который для исходного узла находит кратчайшие пути от него до всех узлов в графе, но это не минимальное остовное дерево.

Swift - Friday Pie
8 апреля 2018 в 08:43
0

Кратчайший путь Дейкстры используется в качестве замены MST, чтобы избежать циклического повторения сообщений по всей сети, такой как WiMaX и некоторые военные радиосети. Думаю, отсюда и путаница.

Ответы (1)

avatar
clemens
8 апреля 2018 в 08:38
5

Вот простой пример:

enter image description here

Алгоритм работает следующим образом:

  1. График имеет серые края.
  2. Добавление некоторых ребер без обнаружения окружности.
  3. После добавления вертикального края алгоритм обнаруживает круг. Последнее ребро (красное) удаляется, так как оно имеет наибольший вес.
  4. Добавление горизонтального края также дает круг. Поскольку он имеет самый большой вес, он удаляется.
  5. Добавление последнего ребра также создаст круг, но последнее добавленное ребро не имеет большого веса. Вместо этого необходимо удалить ребро с весом 3. Минимальное остовное дерево состоит из ребер черного цвета на рисунке (5).

Если вы помечаете посещающие узлы, обнаружение круга выполняется легко. Чтобы найти самый тяжелый край обнаруженного круга, вы используете общий алгоритм поиска кругов.

Примечание: На рисунке (5) показано, почему необходимо посетить все ребра, поскольку (3) уже содержит связующее дерево. Но он не минимален.