|
|
Описание алгоритмов Прима и Дейкстры.
Алгоритм построения минимального стягивающего (остовного) дерева (MST - Mininal Spanning Tree) Прима и алгоритм нахождения кратчайших путей для единственного источника в сетях, имеющих неотрицательные веса, - алгоритм Дейкстры были открыты до изобретения современных структур данных, прежде всего различных реализаций очередей по приоритетам. Поэтому классические реализации этих алгоритмов не приспособлены для работы с графами с большим количеством вершин. Широкомасштабные исследования в области структур данных позволили значительно улучшить производительность этих алгоритмов. Важно также отметить одно сходство этих алгоритмов: они оба являются разновидностями обобщенного поиска на графе, хотя решают разные задачи. В алгоритме Прима строится минимальное остовное дерево, а алгоритм Дейстры, фактически, строит дерево кратчайших путей - SPT(Shortest-Path Tree).
Алгоритм Прима формулируется следующим образом:
1. MST состоит из произвольной вершины.
2. В MST добавляется V-1 вершина, еще не включенная в MST, такая, что ребро, соединяющее ее с MST, является минимальным.
Алгоритм Дейкстры формулируется следующим образом:
1. SPT состоит из вершины источника.
2. В SPT добавляется V-1 вершина, еще не включенная в SPT, такая, что путь из источника в нее является минимальным.
|
|