Изменения

Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <tex>F</tex> ответа в графе <tex>G</tex>, поддерживая приоритетную очередь <tex>Q</tex> из вершин <tex>G \setminus F</tex>. Ключом в куче будет , имеющую ключом для вершины <tex>v</tex> <tex>\min\limits_{u \in F, uv \in EG}w(uv)</tex> (вес минимального ребра из вершин <tex>F</tex> в вершину <tex>v</tex>). Также для каждой вершины очереди будем хранить <tex>p(v)</tex> — вершину <tex>u</tex>, на которой достигается минимум в определении ключа. Дерево <tex>F</tex> поддерживается неявно, а множество его ребер и равно <tex>\left\{\left(v,p(v)\right)|v \in G \setminus \{r\} \setminus Q\right\}</tex>, где <tex>r</tex> — корень <tex>F</tex>. Изначально <tex>F</tex> пусто, в очереди все вершины с ключами <tex>+\infty</tex>. Выберём произвольную вершину <tex>r</tex> и присвоим её ключу <tex>0</tex>. На каждом шаге будем извлекать минимальную вершину <tex>v</tex> из приоритетной очереди и релаксировать все ребра <tex>vu</tex>, такие что <tex>u \in Q</tex>, выполняя при этом <tex>\text{decreaseDECREASE-keyKEY}</tex> и обновление <tex>p(v)</tex>. Ребро <tex>\left(v,p(v)\right)</tex> при этом добавляется к ответу.