Построение коммуникационной сети минимальной длины
Коммуникационная сеть минимальной длины (или дерево кратчайших расстояний) – это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети, т.е. возможность попасть из любого узла в любой другой узел.
Алгоритм:
Начать с любого узла и соединить его с ближайшим узлом. Считаем, что эти узлы связанные, а все другие несвязанные.
Определить несвязанный узел, ближайший к одному из связанных узлов. Если таких «ближайших» узлов несколько, то выбрать любой. Добавить этот узел к связанным. И т.д., до тех пор, пока есть несвязанные узлы.
Пример. Университет устанавливает компьютерную систему электронной почты, которая позволит передавать сообщения между деканами восьми факультетов. Сеть возможных электронных связей между деканатами показана ниже. Протяженность коммуникаций в километрах отмечена на дугах.
Необходимо предложить проект системы связи, которая позволит всем восьми деканам обеспечить доступ к системе электронной почты. Решение должно обеспечить минимальную возможную общую длину коммуникаций.
Длина коммуникаций равна сумме расстояний на дугах:
Задача определения кратчайшего пути Метод присвоения меток
Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.
Пример: Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах – расстояния в километрах.
Надо найти кратчайшие расстояния от склада до каждой строительной площадки.
Каждому узлу приписывают метку из двух чисел:
первое число – минимальное расстояние от узла 7 до данного узла,
второе – номер предыдущего узла на пути от узла 7 к данному узлу.
Помеченным называют узел, для которого определен путь от узла 7. Иначе узел – непомеченный.
Если кратчайшее расстояние от узла 7 до данного узла определено, то соответствующая метка постоянная и обозначается в круглых скобках. Остальные метки временные и обозначаются в квадратных скобках. Узлы с постоянными метками закрашиваем.
Узлу 7 присваиваем метку (0, S), где 0 – расстояние от узла 7, S – обозначение стартового узла.
Узел 7 связан с узлами …. Им присваиваем соответствующие метки –
После выполнения этой операции выполняют два шага:
находят участок минимальной длины и соответствующую временную метку делают постоянной;
узел, которому соответствует данная постоянная метка становится новым стартом.
Метка с наименьшим расстоянием соответствует узлу …. Этот узел объявляем помеченным и заменяем скобки у метки.
Узел … связан непосредственно с узлами без постоянных меток. Временная метка узла … равна [ ]=[ ], а у узла … – [ ]= [ ]. Т.к. узел … уже имеет временную метку [ ], то из двух меток выбираем ту, в которой расстояние меньше, т.е. [ ].
Из всех временных меток [ ], [ ], [ ] выбираем метку с наименьшим первым числом – [ ]. Она становится постоянной и очередной шаг начинаем с узла ….
Этот узел связан только с узлом … без постоянной метки. Временная метка узла … равна [ ]=[ ]. Эта метка имеет меньшее первое число, чем предыдущая, поэтому узлу … приписываем новую временную метку [ ].
Из всех временных меток [ ], [ ] метку с наименьшим первым числом [ ] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла ….
Узел … связан только с одним узлом без постоянной метки – узлом …. Временная метка узла … равна [ ]=[ ].
Из всех временных меток [ ], [ ] метку с наименьшим первым числом [ ] объявляем постоянной и следующий шаг начинаем с соответствующего ей узла ...
Узел … связан с узлами без постоянных меток. Временная метка узла … равна [ ]=[ ], а узла … – [ ]=[ ]. Т.к. узел … уже помечен меткой с меньшим первым числом, то метку не меняем.
Из временных меток [ ], [ ] метка с наименьшим первым числом [ ] становится постоянной и следующий шаг начинаем с соответствующего ей узла ….
Метку узла … меняем на ( )=( ).
Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.
Первое число метки у каждой вершины – это длина кратчайшего пути от узла 7 до данной вершины. Чтобы восстановить кратчайший путь от узла 7 до какой-то вершины, нужно из этой вершины перейти в соседнюю (ее номер – второе число метки) и т.д. до вершины 7.
Определим кратчайшие расстояния от склада до каждой строительной площадки: