Как применить алгоритм Дейкстры для графа, чтобы найти MST таким образом, чтобы результирующее дерево должно было иметь ребро между двумя заданными вершинами? (пример: MST должен включать ребро между X и Y)
Спасибо
Проблема алгоритма Дейкстры
comment
Проверьте этот вопрос
- person dario_ramos schedule 01.06.2011
comment
Дейкстра не находит MST для начала.
- person Waldheinz schedule 01.06.2011
comment
да. В этом случае его нужно изменить
- person coder9 schedule 02.06.2011
Ответы (1)
Алгоритм Дейкстры предназначен для поиска кратчайших путей (не MST), но что-то похожее на алгоритм Дейкстры, модифицированное для поиска минимального остовного дерева, называется алгоритмом Прима. Алгоритм Прима сохраняет дерево, которое растет до тех пор, пока не охватит весь граф. Введенное здесь дополнительное ограничение не представляет особых трудностей: вы просто начинаете с X-Y в качестве дерева.
В частности, учитывая, что ваш MST должен включать ребро (X, Y) (если таких ребер несколько, выберите ребро с наименьшим весом), начните с вашего дерева, имеющего два узла X и Y и ребро между ними. Теперь на каждом шаге выберите наименьшее ребро (u, v), где u находится в вашем дереве, а v снаружи, добавьте узел v и ребро (u, v) в ваше дерево и повторите.
person
ShreevatsaR
schedule
01.06.2011
+1 за алгоритм Прима, очень интересно en.wikipedia.org/wiki/Prim%27s_algorithm
- person Mark Booth; 01.06.2011
Я могу просто сделать это в Prim, но проблема заключается в использовании Dijkstra для поиска MST с указанным ограничением.
- person coder9; 02.06.2011
Дейкстра не найдет вам MST. Рассмотрим простой граф с 3 ребрами, AB стоит 4, BC стоит 5, а AC стоит 7. Дикжстра всегда захочет выбрать AB и AC для кратчайшего пути из AC, равного 7, но общий вес дерева равен 12. Но Прим будет всегда выбирайте AB и BC, так как общий вес дерева равен 9, хотя кратчайший путь от A до C также равен 9. Алгоритмы очень похожи, но я никогда не буду называть то, что ведет себя как более поздняя Дейкстра. Если это домашнее задание, может быть, профессор просто хочет, чтобы вы поняли, как легко Дейкстре разобраться в алгоритме Прим?
- person Rob Neuhaus; 02.06.2011
