Минимальное связующее дерево с использованием алгоритма Дейкстры

Question

Я получил график с ценами и буквами на нем.Моя задача не найти лучший путь от одного узла к другому - это найти минимальное остовное дерево.

Для этой цели я подготовил таблицу и отметил лучший путь для этого дерева.

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

Answer 1

Сам алгоритм Дейкстры не может точно найти минимальное остовное дерево графа.Он предназначен для нахождения кратчайшего пути от исходной вершины ко всем остальным вершинам графа.Из-за этого на каждом шаге алгоритм Дейкстры жадно выбирает следующее ребро, наиболее близкое к исходной вершине.Это продолжается до тех пор, пока исходная вершина не соединится с любой другой вершиной графа.Поэтому на каждом шаге текущий граф, который создается, является остовным деревом предыдущего графа, но сумма весов ребер не минимизируется, поскольку он рассматривает только вершины относительно исходной вершины.

ОднакоАлгоритм Прима, который используется для создания минимального остовного дерева, очень похож по процедуре на алгоритм Дейкстры.Однако на каждом шаге вместо выбора следующего ребра, ближайшего к текущей вершине, на этом шаге он жадно выбирает следующее ребро, ближайшее к любой вершине, находящейся в настоящий момент в минимальном остовном дереве (графике, который он создает).

Answer 2

Использование boost::graph библиотеки.См. Оглавление здесь .В частности, он содержит алгоритмы минимальное связующее дерево Крускала и минимальное связующее дерево Прима .

---

Answer 3

Дейкстры нельзя использовать, чтобы найти MST для графа.Это жадный алгоритм, который находит кратчайший путь между узлами.Таким образом, хотя он минимизирует стоимость перехода от одного узла к другому, он не всегда создает MST для всего графа.Общий вес ребер из Дейкстры не может равняться общему весу MST.