Пример 1. Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов

Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рис. 3 показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.

Рис. 3 – Кабельная сеть телевизионной компании

Начнем выполнение алгоритма построения минимального остовного дерева с выбора узла 1 *(или любого другого узла). Тогда

и

Последовательные итерации выполнения алгоритма представлены на рис. 4. Здесь тонкими линиями показаны ребра, соединяющие узлы, принадлежащие множествам и , среди которых ищется ребро с минимальной стоимостью (длиной). Это найденное ребро показано пунктирной линией. Толстыми сплошными линиями обозначены ребра, соединяющие узлы множества (и которые ранее обозначались пунктирными линиями).

Рис. 4 – Последовательные итерации выполнения алгоритма построения минимального остовного дерева

39. Алгоритмы нахождения кратчайшего пути. Алгоритм Дейкстры.