Минимальное остовное дерево (алгоритм Дейкстры)

Посмотреть описание

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