Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример 1. Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов
Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рис. 3 показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.
Начнем выполнение алгоритма построения минимального остовного дерева с выбора узла 1 *(или любого другого узла). Тогда
и
Последовательные итерации выполнения алгоритма представлены на рис. 4. Здесь тонкими линиями показаны ребра, соединяющие узлы, принадлежащие множествам и , среди которых ищется ребро с минимальной стоимостью (длиной). Это найденное ребро показано пунктирной линией. Толстыми сплошными линиями обозначены ребра, соединяющие узлы множества (и которые ранее обозначались пунктирными линиями).
39. Алгоритмы нахождения кратчайшего пути. Алгоритм Дейкстры.
|