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

В чем разница между алгоритмом минимального связующего дерева и алгоритмом кратчайшего пути?

В моем классе структур данных мы рассмотрели два алгоритма минимального связующего дерева (Прима и Крускала) и один алгоритм кратчайшего пути (Дейкстры).

Минимальное остовное дерево - это дерево в графе, которое охватывает все вершины, а общий вес дерева минимален. Кратчайший путь вполне очевиден, это кратчайший путь от одной вершины к другой.

Чего я не понимаю, так как минимальное связующее дерево имеет минимальный общий вес, разве пути в дереве не будут кратчайшими? Кто-нибудь может объяснить, что мне не хватает?

Любая помощь приветствуется.

Рассмотрим граф треугольников с единичными весами - он имеет три вершины , и все три ребра { x , y } , { x , z } , { y , z } имеют вес 1 . Кратчайший путь между любыми двумя вершинами - это прямой путь, но если вы сложите их все вместе, вы получите треугольник, а не дерево. Каждая коллекция из двух ребер образует минимальное остовное дерево в этом графе, но если (например) вы выберете { x , y } , { y $x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$ , тогда вы пропустите кратчайший путь { x , z } .$\{x,y\},\{y,z\}$$\{x,z\}$

В заключение, если вы сложите все кратчайшие пути, вы не обязательно получите дерево.

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

Однако значение, которое они минимизируют, отличается. Дейкстра выбирает в качестве следующего ребра тот, который ведет от дерева к узлу, еще не выбранному ближе всего к начальному узлу. (Затем при этом выборе расстояния пересчитываются.) Прим выбирает в качестве ребра самый короткий, ведущий из дерева, построенного до сих пор. Итак, оба алгоритма выбрали «минимальное преимущество». Основное отличие заключается в том, что значение выбрано минимальным. Для Дейкстры это длина полного пути от начального узла к узлу-кандидату, а для Prim это просто вес этого единственного ребра.

$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

Что касается Kruskal , это немного отличается. Он решает минимальное остовное дерево, но во время выполнения выбирает ребро, которое может не образовывать дерево, а просто избегает циклов. Таким образом, частичные решения могут быть отключены. В конце концов вы получаете дерево.

Хотя вычисления алгоритмов Минимального связующего дерева и Кратчайшего пути выглядят одинаково, они ориентированы на 2 различных требования.

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

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

Вот пример, чтобы прояснить, почему MST не обязательно дает кратчайший путь между 2 вершинами.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

В случае MST ребра AB. BC будет на MST с общим весом 10. Таким образом, стоимость достижения A к C в MST равна 10.

Но в случае кратчайшего пути кратчайшим путем между A и C является AC, равный 7. AC никогда не был на MST.

Разница заключается в том, что является конечной целью этих алгоритмов.

Дейкстры - Здесь цель состоит в том, чтобы достичь от начала до конца. Вы обеспокоены только этими двумя пунктами и соответственно оптимизируете свой путь.

Krusal's - Здесь вы можете начать с любой точки и посетить все остальные точки на графике. Таким образом, вы не всегда можете выбрать кратчайший путь для любых двух точек. Вместо этого необходимо выбрать путь, который приведет вас к более короткому пути для всех остальных точек.

Я думаю, что пример прояснит ситуацию ..

Охватывающее дерево выглядит как ниже. Это потому, что если мы сложим ребра в этой конфигурации, мы получим наименьшую возможную стоимость : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Глядя на связующее дерево, вы можете ошибочно думать, что оно дает вам кратчайшие пути, но на практике это не так. В качестве примера. Если бы мы хотели перейти от узла (1)к (4)нему, это стоило бы нам 7. Однако, если бы мы использовали алгоритм Дейкстры на исходном графе, мы бы обнаружили, что мы можем перейти непосредственно от узла (1)к (4)со стоимостью 5.

Практический пример, чтобы показать разницу>

Предположим, вы приехали на поезде в город и хотите добраться до вашего отеля.

Вариант 1: Получить такси: Такси будет следовать по кратчайшему пути до отеля от станции. Если водитель должен следовать по пути вдоль дерева кратчайшего пути с центром на станции.

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

(*) На самом деле люди будут жаловаться, если будет использовано минимальное остовное дерево (поездка на автобусе будет слишком длинной). Таким образом, на практике это было бы смешанное решение и использовало бы Альфа-дерево (на полпути между минимальным остовным деревом и кратчайшим путевым деревом).

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

Разрез разбивает график на две составляющие. Это может включать несколько ребер. В MST мы выбираем ребро с наименьшим весом.

Расслабление краев говорит, что, если я знаю расстояние между A и B: dist (a, b) и dist между A и C: dist (a, c), если dist (a, b) + edge (b, c) меньше dist (a, c), тогда я могу расслабить ребро (ac). Расслабив все края, мы получаем кратчайший путь.

Я настоятельно рекомендую смотреть видео на алгоритмах графа от профессора Роберта Седжвика.