Почему дерево, полученное из Крускала, отличается от Дийкстры?

Может ли кто-нибудь объяснить, почему дерево, полученное из Крускала, отличается от Дийкстры ?

Я знаю за то, что крускал работает на невырожденном порядке ребер, но Дейкстра использует преимущество приоритетной очереди, но все еще не может понять, почему полученное дерево от них отличается?

3 3
algorithm dijkstra

3 ответа:

Минимальное связующее дерево не является уникальным.

Алгоритм Крускала выбирает ребро минимальной длины из всех возможных ребер, которые соединяют две различные непересекающиеся компоненты MST, найденные до сих пор. Алгоритм Дейкстры/Прима/Ярника выбирает ребро минимальной длины из всех ребер, которые расширяют единственный компонент MST, найденный до сих пор.

На каждом шаге в общем случае алгоритмы выбирают минимальное ребро из различных наборов возможных значений.

ПС. Ну, если ОП относится к дереву кратчайших путей алгоритма кратчайшего пути Дийкстры ответ заключается в том, что дерево кратчайших путей не обязательно является минимальным связующим деревом, алгоритмы вычисляют разные вещи.

2

Основное отличие, я бы сказал, состоит в том, что при заданном наборе узлов алгоритм Дейкстры находит кратчайший путь между 2 узлами. Что не обязательно охватывает все узлы в графе.

Однако в случае Крускала алгоритм пытается охватить все узлы, сохраняя минимальную стоимость ребра.

Рассмотрим этот график: 

       E
   3 / |
    B  | 3
 5 /3\ |
  /    D
A      | 2
  \    F
 1 \  / 1
    C
   2 \
      G
Алгоритм Дейкстры вернет путь A-C-F-D-E для исходного и конечного узлов A и E, при общей стоимости 7. Однако алгоритм Крускала должен охватывать все узлы, поэтому он будет рассматривать ребра [AC], [CG], [CF], [FD], [DB] и [DE] с общей стоимостью 12.

В Dijkstra игнорируются нерелевантные узлы (те, которые не находятся на пути от источника к месту назначения), например, G и B в этом случае. Результирующий путь, конечно, является деревом, но не охватывает все узлы. Там могут быть миллионы узлов, подключенных к G (предполагая, что они не подключены к другим узлам) что никак не повлияло бы на результат Дейкстры. С другой стороны, Крускал должен был добавить эти узлы к полученному дереву.

4

Они решают разные задачи. Возможно, в некоторых случаях они производят одни и те же деревья (например, граф уже является деревом), но в целом деревья оптимизированы для разных вещей: один находит кратчайший путь из одного источника, другой минимизирует общий вес дерева.

Например, рассмотрим, что мы построили MST с помощью Kruskall. Допустим, все ребра в MST весят 1 и это выглядит более или менее линейно. Предположим, что для перехода от A к Z требуется 5 ребер, поэтому путь от А до Я в МСТ будет стоить 5. Тем не менее, вполне возможно, что исходный граф имел ребро от A до Z с ценой 3 (

1