Изменения
Нет описания правки
== Постановка задачи ==
Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex> минимального веса.
== Алгоритм ==
Пусть <tex>G_0 = (V_0, E_0)</tex> - исходный граф. Если хотя бы одна вершина графа <tex>G_0</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя. Теперь для каждой вершины <tex>u</tex> графа <tex>G_0</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex> и вычтем его вес из весов всех остальных рёбер, входящих в <tex>u</tex>.
== Сложность ==
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V| * |E|)</tex>.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
