Используйте Дейкстру, чтобы найти минимальное остовное дерево?

Question

Дейкстры обычно используется для поиска кратчайшего расстояния между двумя узлами графа.Можно ли использовать его для нахождения минимума связующее дерево?Если да, то как?

Редактировать:Это не домашнее задание, но я пытаюсь понять вопрос старого практического экзамена.

Answer 1

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

Руководство по разработке алгоритмов это лучшая книга, которую я нашел, чтобы ответить на вопросы, подобные этому.

Answer 2

Ответ - нет.Чтобы понять почему, давайте сначала сформулируем вопрос так:

Вопрос:Для связного неориентированного взвешенного графа G = (V, E, w) только с неотрицательными весами ребер, образует ли предшествующий подграф, созданный алгоритмом Дейкстры, минимальное остовное дерево G?

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

А: Алгоритм Дейкстры на каждом шаге жадно выбирает следующее ребро, ближайшее к некоторому исходная вершина s.Он делает это до тех пор, пока s не соединится с каждой другой вершиной графа.Очевидно, что созданный подграф-предшественник представляет собой связующее дерево G, но минимизирована ли сумма весов ребер?

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

Контрпример:Рассмотрим неориентированный граф G = (V, E, w) где

V = { a, b, c, d }

E = { (a,b), (a,c), (a,d), (b,d), (c,d) }

w = { ( (a,b) , 5 ) ( (a,c) , 5 ) ( (a,d) , 5 ) ( (b,d) , 1 ) ( (c,d) , 1 ) }

Брать a в качестве исходной вершины.

Алгоритм Дейкстры дает преимущество { (a,b), (a,c), (a,d) }.
Таким образом, общий вес этого остовного дерева равен 5 + 5 + 5 = 15.

Алгоритм Прима берет верх { (a,d), (b,d), (c,d) }.
Таким образом, общий вес этого остовного дерева равен 5 + 1 + 1 = 7.

Answer 3

Алгоритм Прима использует тот же основной принцип, что и алгоритм Дейкстры.

Answer 4

Я бы придерживался жадного алгоритма, такого как алгоритм Прима или Крускала.Я боюсь, что Джикстра не подойдет просто потому, что он минимизирует стоимость между парами узлов, а не для всего дерева.

Answer 5

Конечно, можно использовать Дейкстру для минимального связующего дерева:

dijsktra(s):
dist[s] = 0;
while (some vertices are unmarked) {
    v = unmarked vertex with 
    smallest dist;
    Mark v; // v leaves “table”
    for (each w adj to v) {
        dist[w] = min[ dist[w], dist[v] + c(v,w) ];
    }
}

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

Дальнейшее объяснение вы можете найти в книге «Основы алгоритмов», глава 4, раздел 2.

Надеюсь, это поможет