минимального остова отличается от другого

Question

Предположим, мы дали

неориентированный граф g, где каждый узел я, 1 < = я < п связан со всеми J, I < J < = п

и источник s.

Мы хотим, чтобы найти общую стоимость (определяются как сумма весов всех ребер) на дешевом минимального остовного дерева, которое отличается от минимального расстояния дерева s (т.е. от МСТ, полученного путем запуска чопорных/Алгоритма Дейкстров на s) по крайней мере одним ребром.

Что было бы лучшим способом справиться с этим? Поскольку в настоящее время, я могу только думать о каком-то фиксированная точке итерация

1. запустить DIJKSTRA на (g,s) для получения справочного графика r, что мы должны отличаться от
2. costs := sum(edge_weights_of(r))
3. change := 0
4. для каждой вершины u в r, запустите bfs и отметьте для каждой достигнутой вершины v самый длинный край на пути от u до v.
5. итерация по всем краям e = (a,b) в g: и найти e'=(a',b'), что не в r и сводит к минимуму newchange := weight(e') - weight(longest_edge(a',b'))
6. если (first_time_here ИЛИ newchange < 0), то change += newchange
7. если (newchange < 0) goto 4
8. result := costs + change

Это, кажется, отнимает много времени ... Оно зависит от того, что добавление края t o остовное дерево создает цикл, из которого мы можем удалить самое длинное ребро.

Я также подумал об использовании Kruskal для получения общего минимального остовного дерева и только с использованием вышеприведенного алгоритма для замены одного края, когда деревья из обоих, prim и kruskal, оказались одинаковыми, но это не кажется работать как результат будет сильно зависеть от краев, выбранных во время прогона kruskal.

Любые предложения/подсказки?

Answer 1

Вы можете сделать это с помощью алгоритма Prim`s

Prim's algorithm: 
let T be a single vertex x 
while (T has fewer than n vertices) 
{ 
    1.find the smallest edge connecting T to G-T 
    2.add it to T 
} 

Теперь позволяет изменять его.

Позволяет иметь одно минимальное остовное дерево. Скажем, дерево (E, V)
Используя этот алгоритм

Prim's algorithm (Modified): 
let T be a single vertex 
let isOther = false 
while (T has fewer than n vertices) 
{ 
    1.find the smallest edge (say e) connecting T to G-T 
    2.If more than one edge is found, { 
     check which one you have in E(Tree) 
     choose one different from this 
     add it to T 
     set isOther = true 
     } 
     else if one vertex is found { 
     add it to T 
     If E(Tree) doesn`t contain this edge, set isOther = true 
     Else don`t touch isOther (keep value). 
     } 
} 
If isOther = true, it means you have found another tree different from Tree(E,V) and it is T, 
Else graph have single minimum spanning tree