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

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

неориентированный граф g, где каждый узел i, 1 ‹= i‹ n связан со всеми j, i ‹j‹ = n

и источник s.

Мы хотим найти общие затраты (определяемые как сумма весов всех ребер) самого дешевого минимального остовного дерева, которое отличается от дерева минимальных расстояний s (т. Е. От MST, полученного запуском prim / dijkstra на 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. if (first_time_here OR newchange < 0) then change += newchange
  7. если (новое изменение ‹0) goto 4
  8. result := costs + change

Кажется, это напрасная трата времени ... Это основано на том факте, что добавление ребра к остовному дереву создает цикл, из которого мы можем удалить самое длинное ребро.

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

Есть предложения / подсказки?


graph algorithm minimum-spanning-tree
person User1291    schedule 27.12.2015    source источник
comment
Не правда ли, маловероятно, что эти деревья все равно такие же? Я думаю, вам следует изучить, при каких обстоятельствах дерево минимального расстояния от s совпадает с MST. Я предполагаю, что это очень специфические обстоятельства (s находится в центре графика, что бы это ни значило формально).   -  person Vincent van der Weele    schedule 27.12.2015

Ответы (1)


arrow_upward
2
arrow_downward

Сделать это можно с помощью алгоритма Прима.

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
}

Теперь давайте изменим его.

Пусть у вас есть одно минимальное остовное дерево. Say Tree (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
person Gor    schedule 28.12.2015