Задача алгоритма Дейкстры - PullRequest
1 голос
/ 01 июня 2011

Как применить алгоритм Дейкстры для графа, чтобы найти MST таким образом, что результирующее дерево должно иметь ребро между двумя заданными вершинами?(например, MST должен содержать ребро между X и Y)

Спасибо

1 Ответ

5 голосов
/ 01 июня 2011

Алгоритм Дейкстры для кратчайших путей (не MST), но что-то похожее на алгоритм Дейкстры, модифицированный для поиска минимального остовного дерева, называется алгоритмом Прима. Алгоритм Прима поддерживает дерево, которое растет, пока не охватит весь граф. Введенное здесь дополнительное ограничение не представляет особых трудностей: вы просто начинаете с X-Y в качестве дерева.

В частности, учитывая, что ваш MST должен включать ребро (X, Y) (если таких ребер несколько, выберите один с наименьшим весом), начните с того, что у вашего дерева есть два узла X и Y и ребро между ними. Теперь на каждом шаге выберите наименьшее ребро (u, v), где u находится в вашем дереве, а v снаружи, добавьте узел v и ребро (u, v) к своему дереву и повторите.

...