Как запустить алгоритм Дейкестры, чтобы сделать его похожим на Prim и сгенерировать MST?

Предположим, я запускаю алгоритм Дейкстры для посещения всех узлов (вместо исходного начального узла и узла назначения), т.е. я проверяю, все ли узлы посещены или нет, вместо узла назначения. Будет ли этот алгоритм генерировать MST (минимальное связующее дерево)? (и это похоже на Прим?)


algorithm dijkstra minimum-spanning-tree
person sheidaei    schedule 10.02.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Нет. Рассмотрим граф, который выглядит как квадрат, три ребра стоят 1, а оставшееся — 2. Стоимость MST для этого графа составляет 3, но если вы запустите свой алгоритм Дейкстры на вершине, содержащей дорогое ребро, будет выбрано именно это, поскольку это кратчайший путь к соединенному узлу.

Крутая визуализация ASCII:

    1
 A------B
 |      |
1|      |1
 |      |
 C------D
    2

Если вы начинаете Dijkstra в C, CD будет кратчайшим путем из C в D, но он не может содержаться в MST.

person us2012    schedule 10.02.2013
comment
Моя цель не в том, чтобы перейти от C к D, я собираюсь начать с C, и пока есть узел, который не виден, я собираюсь продолжать добавлять узлы. Итак, я собираюсь выбрать A, затем B, затем D. Это MST. - person sheidaei; 10.02.2013
comment
Тогда это не Дейкстра. Дейкстра в целом представляет собой алгоритм, который находит кратчайшие пути от выделенного узла ко всем другим узлам. В этом случае вы должны сделать описание алгоритма, о котором вы на самом деле говорите, более точным. - person us2012; 10.02.2013
comment
Я предполагаю, что вы правы, тот, который я имел в виду, больше похож на Prime, чем на Дейкстру, поскольку Дейкстра вычисляет кратчайший путь из одного узла, он не создает MST - person sheidaei; 10.02.2013

arrow_upward
0
arrow_downward

Он не будет генерировать MST, как показано на этом примерном графике:

              ... A
 .... 10 -''''    \
S                  2
 '''' 11 -....      \
              ''''' B

Если мы запустим алгоритм Дейкстры в узле S, результирующее дерево будет выглядеть так:

              ... A
 .... 10 -''''    
S                 
 '''' 11 -....    
              ''''' B

Имея общую длину ребра 21, в то время как (в данном случае уникальный) MST будет:

              ... A
 .... 10 -''''    \
S                  2
                    \
                    B

В итоге получилось 12.

person jix    schedule 10.02.2013