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

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

Описание

На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.

Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Таким образом, при выполнении каждого шага алгоритма, высота формируемого дерева увеличивается на 1. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

Пример работы

Алгоритм начинает свою работу с вершины A. На третьем шаге, рёбра BD и AB имеют вес 2, поэтому ребро BD выбирается произвольно. После этого шага, ребро AB более не является кандидатом на добавление в дерево, так как данное ребро связывает два узла, которые уже находятся в дереве.

Оценка

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево.

• Массив, списки смежности (матрица смежности) — O(V²)
• Бинарная пирамида, списки смежности — O((V+E) log V) = O(E log V)
• Фибоначчиева пирамида, списки смежности — O(E + V log V)