Использовать Dijkstra для нахождения Минимального Связующего дерева?
Dijkstra обычно используется для нахождения кратчайшего расстояния между двумя узлами в графике. Это может использоваться для нахождения минимального связующего дерева? Если так, как?
Править: Это не домашняя работа, но я пытаюсь понять вопрос на старом экзамене практики.
3 ответа
Строго говоря, нет. Алгоритм Дейкстры находит кратчайший путь между двумя вершинами на графе. Однако очень небольшое изменение алгоритма приводит к другому алгоритму, который действительно создает MST.
Руководство по разработке алгоритмов - лучшая книга, которую я нашел, чтобы ответить на вопросы, подобные этому.
Алгоритм Прима использует тот же основной принцип, что и алгоритм Дейкстры.
Я бы придерживался жадных алгоритмов, таких как Prim или Kruskal. Я боюсь, что Djikstra не подойдет просто потому, что он минимизирует затраты между парами узлов, а не для всего дерева.