Специальность 071800 (Мехатроника) (стр. 14 )

ІІІ) Как только количество отобранных ребер должно быть на одно меньше числа вершин, отбор прекращается. Полученное дерево является минимальным соединением.

Вес минимального соединения графа G

2. Найдем кратчайший путь от до , используя алгоритм Дейкстры, основанный на присвоении меток вершинам и пересчете меток; получаемые при этом постоянные метки и есть длины кратчайших путей.

Присвоим вершине (начальной) метку и будем считать ее постоянной, а всем остальным вершинам — метки , их будем считать временными. Положим — множеству вершин, смежных с и имеющих временные метки. Для всех вершин меняем метки по правилу: Среди всех вершин с временными метками находим , метка которой минимальна и делаем ее постоянной; . Возвращаемся к II до тех пор, пока вершина (конечная) не получит постоянной метки. Постоянные метки вершин и дают длины кратчайших путей от до этих вершин. Для построения самого пути движемся в обратном направлении от конечной вершины к начальной по убыванию меток так, чтобы разница между метками смежных вершин равнялась длине ребра.

На множестве вершин, смежных с , найдем такую , что

.  (1)

Аналогично, на множестве вершин, смежных с , найдем такую , что , и так далее.

После некоторого числа шагов вершина совпадает с вершиной , путь — кратчайший, а его длина .

Решим задачу по алгоритму Дейкстры (каждый шаг — присвоение одной постоянной метки).

1 шаг.  .                                         — постоянная метка.

— временные метки.

2 шаг. 

 

 

Метка — наименьшая из всех временных меток, делаем ее постоянной.

— постоянная метка.

3 шаг. 

 

 

Наименьшие из всех временных меток имеют вершины и . Выбираем, например, .

— постоянная метка.

4 шаг. 

  .

Метки не изменились, наименьшей из всех временных осталась метка 3, принадлежащая вершине .

— постоянная метка.

5 шаг. 

  .

— постоянная метка.

6 шаг. 

 

 

  .

— постоянная метка.

7 шаг. 

— постоянная метка.

8 шаг. 

— постоянная метка.

9 шаг. 

  .

— постоянная метка.

10 шаг.  Последняя вершина получает последнюю постоянную метку

— постоянная метка.

Строим путь, начиная с конечной вершины. Из вершин и , смежных с , выбираем ту, для которой выполняется равенство (1):

для :

9=8+1  верно;

для :

9=6+4  неверно.

Значит, выбираем вершину .

Из вершин, смежных с выбираем ту, для которой выполняется равенство (1). Это будет вершина .

Из вершин, смежных с выбираем ту, для которой выполняется равенство (1). Это могут быть вершины и , оставим . Вершина смежна и выполняется равенство (1). Значит, кратчайший путь от до :