120
правок
Изменения
добавленн пример
<tex>\text{decrease-key}(Q, u, key[u]) </tex>
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
==Пример==
{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
! Изображение !! Множество вершин !! Описание
|-
|[[Файл:Mst_prima_1.png|200px]]
|
{|
| '''a''' || '''b''' || '''c''' || '''d''' || '''e'''
|-
| <tex> 0 </tex> || <tex> \inf </tex> || <tex> \inf </tex> || <tex> \inf </tex> || <tex> \inf </tex>
|}
| Извлечём из множества вершину '''a''', так как её приоритет минимален, и рассмотрим её соседей '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты и добавим в ответ рёбра '''ab''', '''ac''', и '''ae'''.
|-
|[[Файл:Mst_prima_2.png|200px]]
|
{|
| <s>a</s> || '''b''' || '''c''' || '''d''' || '''e'''
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> \inf </tex> || <tex> 1 </tex>
|}
| Теперь минимальный приоритет у вершины '''е'''. Извлечём её и рассмотрим её соседей.<br/>Изменим приоритет только у вершины '''d''',так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и добавим в ответ ребро '''ed'''.
|-
|[[Файл:Mst_prima_3.png|200px]]
|
{|
| <s>a</s> || '''b''' || '''c''' || '''d''' || <s>e</s>
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 7 </tex> || <tex> 1 </tex>
|}
| После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующий вершины - '''c''',<br/>будет обновлён потенциал у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.
|-
|[[Файл:Mst_prima_4.png|200px]]
|
{|
| <s>a</s> || <s>b</s> || <s>c</s> || '''d''' || <s>e</s>
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 2 </tex> || <tex> 1 </tex>
|}
| Далее будет рассмотрена следующая вершина - '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого в заданном множестве не останется вершин, которые не были бы рассмотрены,<br/>алгоритм завершит работу, так как минимальное остовное дерево будет построено.
|}
== Корректность ==
