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

Задача о кратчайшем пути между двумя пунктами.

Задача определения кратчайшего пути.

Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой.

Пример: узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах расстояния в километрах.

Надо найти кратчайшие расстояния от склада до каждой строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки 1? Проходит ли кратчайший путь от склада до строительной площадки 1 через строительную площадку 2?

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

Изначально узлу 7 присваиваем метку (0,S), где 0 – расстояние от узла 7 – обозначение стартового узла.

Узел 7 связан с узлами 2,4,6. Длины соответствующих ребер – 17,5,6. Поэтому узлам 2,4,6 присваиваем временные метки -- .

Временная метка с наименьшим расстоянием до узла 7 становится постоянной. Это метка (5,7) узла 4. Поэтому следующий шаг начинаем с узла 4.

Узел 4 связан с узлами 2 и 5 без постоянных меток. Длина ребра 4 -- 5 равна 4, метка узла 4 – (5,7) временная метка узла 5 равна . Длина ребра 4 -- 2 равна 6, метка узла 4 – (5,7) временная метка узла 2 равна . Узел 2 помечен меткой , но 11<17 старую метку узла 2 меняем на новую временную метку , где 11 – длина пути от узла 7 до узла 2, 4 – номер предшествующего узла.

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

Этот узел связан с узлом 5 без постоянной метки. Длина ребра 6-5 равна 2, метка узла 6 – (6,7) временная метка узла 5 равна . Но узел 5 уже помечен меткой . Так как 8<9, то узлу 5 припишем новую метку . После этого из всех временных меток метку с наименьшим первым числом объявим постоянной, а следующий шаг начнем с соответствующего ей узла 5.

Узел 5 связан только с одним узлом без постоянной метки – узлом 3. Длина ребра 5-3 равна 4, метка узла 5 -- временная метка узла 3 равна . Теперь из временных меток метку с наименьшим первым числом объявляем постоянной, а следующий шаг начнем с соответствующего ей узла 2.

Узел 2 связан с узлами 1 и 3 без постоянных меток. Длина ребра 2-1 равна 15, метка узла 2 -- узлу 1 припишем временную метку . Длина ребра 2-3 равна 3, метка узла 2 -- можно пометить узел 3 временной меткой , но узел 3 уже помечен меткой с меньшим первым числом. Поэтому метку 3 не меняем. Теперь из временных меток метка с наименьшим первым числом становится постоянной , а с соответствующего ей узла 3 начнем следующий шаг. Метку узла 1 меняем на . Всем узлам приписаны постоянные метки. Действие алгоритма прекращается.

Первое число метки у каждой вершины – это длина кратчайшего пути от узла 7 до данной вершины. Чтобы восстановить кратчайший путь от узла 7 до какой-то вершины, нужно из этой вершины перейти в соседнюю (ее номер – это второе число метки). И так до вершины 7.

Теперь можно ответить на вопросы задачи. Метка узла 1 -- длина кратчайшего пути от узла 7 до узла 1 равна 22. Из узла 1 идем в узел 3. Метка узла 3 -- идем в узел 5. Метка узла 5 -- идем в узел 6. Метка узла 6 -- идем в узел 7, т.е. кратчайший путь 1-3-5-6-7. Он не проходит через узел 2.

Задачи.

1. Компания грузовых перевозок осуществляет услуги по перевозке грузов между Воронежем (В) и райцентрами. Так как существенны быстрое обслуживание и минимальные транспортные затраты, то необходим наиболее короткий маршрут. Рисунок отображает сеть дорог. Расстояния указаны в километрах. Найти кратчайшие маршруты от Воронежа до всех 10 райцентров. Какова длина кратчайшего пути от Воронежа до райцентра 10? Проходит ли кратчайший путь от Воронежа до райцентра 9 через райцентр 6?

2. Предложить алгоритм действий при наличии в сети нескольких равных постоянных меток.

Известна схема дорог. Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.

Пример:Найдем маршрут минимальной длины от пункта 1 к пункту 11.

Припишем вершинам числа вместо номеров. Для 11-й вершины это 0.

11-я вершина соединена с 8-й, 9-й и 10-й вершинами, которым припишем числа 0+5=5, 0+5=5, 0+4=4 соответственно. Все эти ребра покажем двумя чертами со стрелками.

По числам 8-й и 9-й вершин найдем число 5-й вершины: min(5+7, 5+8)=12. Ребро (5,8) изобразим двумя чертами со стрелкой.

По числам 9-й и 10-й вершин найдем число 6-й вершины: min(5+7, 4+3)=7. Ребро (6,10) изобразим двумя чертами со стрелкой.

По числам 9-й и 10-й вершин найдем число 7-й вершины: min(5+4, 4+6)=9. Ребро (7,9) изобразим двумя чертами со стрелкой.

По числу 5-й вершины определим число 2-й вершины: 12+7=19. Ребро (2,5) изобразим двумя чертами со стрелкой.

По числам 5-й, 6-й и 7-й вершин определим число 3-й вершины: min(12+2, 9+2, 7+6)=11. Ребро (3,7) изобразим двумя чертами со стрелкой.

По числам 6-й и 7-й вершин найдем число 4-й вершины: min(7+3, 9+8)=10. Ребро (4,6) изобразим двумя чертами со стрелкой.

По числам 2-й, 3-й и 7-й вершин определим число 1-й вершины: min(19+1, 11+5, 10+4)=14. Ребро (1,4) изобразим двумя чертами со стрелкой. Длина кратчайшего пути равна 14.

Двигаемся из начальной вершины 1 в конечную вершину 11 по ребрам со стрелкой. Получаем кратчайший путь 1-4-6-10-11. Его длина равна 14.

Задача.

1. Найти маршрут минимальной длины от пункта 1 к пункту 10.

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

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

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

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

Пример.Университет устанавливает компьютерную систему электронной почты между деканатами.

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

Начинаем с узла 1. Ближайший к нему узел – это узел 2 на расстоянии 2. Считаем, что узлы 1,2 – свзанные, и отметим это двойной чертой.

Ближайшие несвязанные узлы к одному из связанных узлов 1 и 2 – это узлы 3 и 6. Выбираем любой из них, например узел 3. Ребро 1-3 отметим двойной чертой и считаем узлы 1,2,3 связанными.

Далее ищем ближайший несвязанный узел к узлам 1,2,3,. И т.д.. В результате получим минимальное дерево.

Его длина равна сумме расстояний на дугах: 2+3+1+1+0,5+1+2=10,5 (км).

Задача.

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