Изменения

Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex> минимального веса.

Понятно, что если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым. Пусть теперь такого дерева нет.<br>Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям из <tex>u</tex>). При этом вес нашего дерева не изменится.<br>Теперь построим граф <tex>C</tex> - конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> - две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>В графе <tex>C</tex> содержится меньше вершин, чем в графе <tex>G_0</tex>. Иначе, если бы в <tex>C</tex> было бы столько же вершин, сколько в <tex>G_0</tex>, то в <tex>K</tex> все компоненты сильной связности состояли бы из единственной вершины. Значит в <tex>G_0</tex> с весовой функцией <tex>w'</tex> не было бы нулевых циклов. То есть мы смогли бы построить в <tex>K</tex> остовное дерево с корнем в <tex>v</tex>, что противоречит нашему предположению.<br>Предположим теперь, что в <tex>C</tex> уже построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по нулевым путям из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> - компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по нулевым путям из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex> и получим дерево <tex>T'</tex> - MST в графе <tex>G_0</tex>.

Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V| * |E|)</tex>.