Изменения

Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex>(иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> - применим <tex>\mathbbmathtt{decrease - key}</tex> к <tex>u</tex>. Эта операция либо переместила <tex>u</tex> внутри <tex>B</tex>, либо определила, что метка <tex>d(u)</tex> точна и переместила <tex>u</tex> в <tex>F</tex>.Если же <tex>u \notin F \hspace{2 mm} \& \hspace{2 mm} u \notin B</tex>, мы применим операцию <tex>\mathbbmathtt{insert}</tex>, и <tex>u</tex> запишется в