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

Question

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

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

Answer 1

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

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

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

A: Алгоритм Дейкстры на каждом шаге жадно выбирает следующее ребро, ближайшее к некоторой исходной вершине 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 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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) ];
    }
}

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

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

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