Донской Технический Государственный Университет

Задача о кратчайшем остовном дереве (Алгоритм

Краскала. Алгоритм Прима-Декстры. Алгоритм Дейкстры)

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

составляющих этот путь, если

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

Неориентирован ный граф с шестью вершинами и семью рёбрами

Описание

•Задача о кратчайшем пути. Классическим примером сетевых задач является определение кратчайшего пути между вершинами сети. Пусть задан граф (I, D, G), каждой дуге которого поставлено в соответствие число c, называемое длиной. Также пусть выделены две вершины графа s и t, и требуется найти путь наименьшей длины, ведущий из вершины s в вершину t.

•Если в графе имеются «кратные» дуги, соединяющие одинаковые начало и конец, то достаточно оставить одну — с наименьшей длиной, а остальные отбросить. Таким образом, достаточно рассматривать задачу о кратчайшем пути для простого графа (I, D), в котором дуги определяются упорядоченными парами вершин d = (i, j). Тогда естественно путь L, идущий из вершины s в вершину t, задавать св виде упорядоченного набора вершин, через которые проходит данный путь:

•а длины дуг обозначать как c = c[i,j].

•Длина описанного выше произвольного пути L определяется по формуле

•Легко заметить, что задача о кратчайшем пути является частным

случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам

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

решение ее специальными (частными)

методами.

Алгоритм Краскала

•Алгоритм Краскала в псевдокоде:

•Kruskal's algorithm:

•sort the edges of G in increasing order by length

•keep a subgraph S of G, initially empty

•for each edge e in sorted order

•	if the endpoints of e are
	disconnected in S

•add e to S

•return S

показана схема работы алгоритма Прима с корнем r

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

работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Краскала

принять за O(E).

Алгоритм Прима-Дейкстры

•Алгоритм Прима-Дейкстры —

алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примой в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

Описание

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

Вход

Связный неориентированный граф G(V,E) Выход

Множество T рёбер минимального остовного дерева Реализация

Обозначения

d[i] — расстояние от i-й вершины до построенного дерева

p[i] — предок i-й вершины, то есть такая вершина u, что (i,u) легчайшее из всех рёбер соединяющее i с вершиной из построенного дерева.

w(i,j) — вес ребра (i,j)

Q — приоритетная очередь вершин графа, где ключ — d[i] T — множество ребер минимального остовного дерева

Оценка

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь Q реализована как обычный массив d, то Extract.Min(Q) выполняется за O(n), а стоимость операции составляет O(1). Если Q представляет собой бинарную пирамиду, то стоимость Extract.Min(Q) снижается до O(logn), а стоимость возрастает до O(logn). При использовании фибоначчиевых пирамид операция

Extract.Min(Q) выполняется за O(logn), а за O(1).