У меня возникли проблемы с поиском примера алгоритма для минимального остовного дерева Дейкстры. Я уже знаю об алгоритме единственного кратчайшего пути Дейкстры, но не о связующем дереве. У меня есть простое объяснение от класса:
Для каждого ребра добавьте его в дерево. Если обнаружен цикл, удалите самый тяжелый край.
Я облазил Интернет и не смог найти алгоритм для этого.
Возможно, мне нужно просто написать код для себя, но я решил спросить, есть ли у кого-нибудь хороший пример.
Кто-нибудь может помочь?
Вероятно, потому, что он более известен как Алгоритм Прима.
@StoryTeller Нет, я так не думаю. В частности, я не знаю ни одного алгоритма, который удаляет ребра — ни Крускал, ни Прим (алгоритм ) этого не делают.
@user202729 user202729 - Ну, я знаю только один алгоритм поиска MST, который приписывается Дейкстре. В любом случае материал класса OP кажется неточным.
Это также известно как проблема дерева Штейнера? Если да, то загляните на grass.osgeo.org/grass70/manuals/v.net.steiner.html, я думаю, что найти исходники тоже не проблема.
Может ли это быть алгоритм обратного удаления en.m.wikipedia.org/wiki/Reverse-delete_algorithm?
Такого нет. Дейкстры — алгоритм поиска кратчайшего пути.
Есть два популярных алгоритма MST: Крускала и Прима. Нет и того, что вы описали. Существует вариант кратчайшего пути Дейкстры, который для исходного узла находит кратчайшие пути от него до всех узлов в графе, но это не минимальное остовное дерево.
Кратчайший путь Дейкстры используется в качестве замены MST, чтобы избежать циклического повторения сообщений по всей сети, такой как WiMaX и некоторые военные радиосети. Думаю, отсюда и путаница.