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

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

Задачи определения кратчайшего пути можно решить с использованием метода присвоения меток, когда каждому узлу присваивается метка из двух чисел.

Первое число – минимальное расстояние от стартового узла до данного узла.

Второе число – номер предыдущего узла на пути от стартового узла к данному узлу.

Узел, для которого определяется путь от стартового узла, назовем помеченным.

Узел, для которого такой путь еще не определен, назовем непомеченным.

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

Все остальные метки – временные и обозначаются в квадратных скобках.

Узлы с постоянными метками будем закрашивать.

Пример 1: Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах – расстояния в километрах. Надо найти кратчайшие расстояния от склада до строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки? Проходит ли кратчайший путь от склада к строительной площадке 1 через строительную площадку 2? Какова длина кратчайшего пути от склада до строительной площадки 2? Проходит ли кратчайший путь от склада к строительной площадке 2 через строительную площадку 4?

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

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

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

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

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

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

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

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

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

Двигаясь от конечного пункта к начальному пункту, каждой вершине припишем число по определенным правилам. Конечной вершине присвоим число 0. Если i-я вершина в направлении от начального пункта к конечному пункту непосредственно соединена с вершинами j₁,…, j_k, которым приписаны числа r(j₁),…, r(j_k), то вершине i приписывается число r(i) = (r(j_s) + t(i, j_s)), где t(i, j_s) – длина ребра (i, j_s).

Пусть этот минимум достигается для вершины j_m. Тогда ребро (i, j_m) покажем двумя чертами со стрелкой от i к j_m. Если таких j_m несколько, то на этом шаге будет несколько двойных ребер.

Число, приписанное начальному пункту, равно минимальной длине искомого маршрута. Двигаться от начального пункта к конечному пункту нужно по двойным ребрам со стрелками.

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