Построение коммуникационной сети минимальной длины

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

Алгоритм построения:

1. начать с любого узла и соединить его с ближайшим узлом. Считаем, что это связанные узлы, а все другие узлы – несвязанные;

2. определить несвязанный узел, ближайший к одному из связанных узлов. Если таких «ближайших» узлов несколько, то выбрать любой. Добавить этот узел к связанным. И т.д. до тех пор, пока есть несвязанные узлы.

Пример 2. Университет устанавливает компьютерную систему электронной почты, которая позволит передавать сообщения между деканами восьми факультетов. Сеть возможных электронных связей между деканатами показана ниже.

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