Dijkstra's обычно используется для нахождения кратчайшего расстояния между двумя узлами в графе. Его можно использовать для поиска минимального spanning tree? Если да, то как?
Изменить: это не домашнее задание, но я пытаюсь понять вопрос о старом экзамене.
Строго, ответ - нет. Алгоритм Дейкстры находит кратчайший путь между двумя вершинами на графике. Однако очень небольшое изменение алгоритма создает еще один алгоритм, который эффективно генерирует MST.
Руководство по разработке алгоритмов - лучшая книга, которую я нашел, чтобы ответить на такие вопросы, как этот.
Ответ - нет. Чтобы понять, почему, сначала сформулируйте вопрос так:
G = (V, E, w) с только неотрицательными весами ребра предшествующий подграф, созданный алгоритмом Дейкстры, образует минимальное остовное дерево G?(Обратите внимание, что неориентированные графы являются специальным классом ориентированных графов, поэтому вполне нормально использовать Алгоритм Дейкстры на неориентированных графах. Кроме того, MST определены только для связанных неориентированных графов и тривиальны, если граф не взвешен, поэтому мы должны ограничить наш запрос этими графами.)
A: Dijkstra Algorithm на каждом шагу жадно выбирает следующее ребро, которое ближе всего к некоторой исходной вершине s. Он делает это до тех пор, пока s не будет подключен ко всем другим вершинам графика. Очевидно, что предшественник-подграф, который создается, является связующим деревом G, но является ли сумма краев весом минимизирована?
Prim Algorithm, который, как известно, создает минимальное связующее дерево, очень похож на алгоритм Дейкстры, но на каждом этапе он жадно выбирает следующее кромку, которое ближе всего к любой вершине в настоящее время в рабочем 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.
Prim Algorithm принимает ребра { (a,d), (b,d), (c,d) }.
Таким образом, общий вес этого связующего дерева 5 + 1 + 1 = 7.
Алгоритм Prim использует тот же базовый принцип, что и алгоритм Дейкстры.
Я буду придерживаться жадного алгоритма, такого как Prim или Kruskal's. Я боюсь, что Djikstra не будет делать этого, просто потому, что он минимизирует стоимость между парами узлов, а не для всего дерева.
Конечно, можно использовать 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.
Надеемся на эту помощь