Алгоритм двух китайцев

Постановка задачи

Дан взвешенный ориентированный граф $G(V, E)$, в нем необходимо найти минимальное остовное дерево с заданным корнем.

Определение:
Остовное дерево в ориентированном графе $G(V, E)$ —это такой ациклический подграф нашего графа $G$, что выделена вершина $root -$ корень дерева, и в каждую вершину, кроме $root$, входит ровно одно ребро, а в $root$ не входит ни одного ребра.

Медленный алгоримт

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

Докажем корректность алгоритма:

потом...

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana