7.6. Экстремальные пути в нагруженных ориентированных графах

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

Пример. Для графа, изображенного на рис. 24, матрица весов имеет вид: .

Длина пути равна .

Рис. 24. Нагруженный ориентированный граф

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

Диаметром графа называется величина .

Максимальным удалением (эксцентриситетом) в графе от вершины называется величина . Радиусом графа называется величина . Центром графа называется любая вершина такая, что .

Алгоритм поиска минимального пути из в в ориентированном графе (алгоритм фронта волны):

1) Помечаем вершину индексом 0, затем помечаем вершины принадлежащие образу вершины индексом 1. Обозначаем их . Полагаем .

1. Если или , и одновременно то вершина не достижима из . Работа алгоритма заканчивается. В противном случае продолжаем.

2. Если , то переходим к шагу 4. В противном случае мы нашли минимальный путь из в и его длина равна . Последовательность вершин

есть этот минимальный путь. Работа завершается.

3. Помечаем индексом все непомеченные вершины, которые принадлежат образу множества вершин c индексом . Множество вершин с индексом обозначаем . Присваиваем и переходим к шагу 2. Множество называется фронтом волны -го уровня.

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

Для того, чтобы найти расстояния в ориентированном графе, необходимо составить матрицу расстояний между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю ( , ). Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний ( , если ). Далее построчно заполняем матрицу следующим образом. Рассматриваем первую строку, в которой есть единицы. Пусть это строка -тая и на пересечении с -тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем -тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать .

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

Пример. Найдем расстояния в ориентированном графе , изображенном на рис. 26.

В данной задаче количество вершин , следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа будут иметь размерность .

Рис. 26

Матрица смежности: .

Начинаем заполнять матрицу минимальных расстояний: сначала ставим нули по главной диагонали и , если , (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, , . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому . В итоге получаем следующую матрицу: .

Таким образом, диаметром исследуемого ориентированного графа будет .

Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе от вершины нее:

.

Значит, радиусом графа будет .

Соответственно, центрами графа будут вершины и , так как величины их эксцентриситетов совпадают с величиной радиуса .

Опишем теперь нахождение минимального пути из вершины в вершину по алгоритму фронта волны. Обозначим вершину как , а вершину  как (рис. 27).

Рис. 27

Множество вершин, принадлежащих образу , состоит из одного элемента  это вершина , которую, согласно алгоритму, обозначаем как : . Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня  это множество вершин, принадлежащих образу вершины : , обозначаем . В образ вершины входят две вершины  и , но, так как уже была помечена как , то фронт волны третьего уровня состоит из одного элемента: , . Из непомеченных вершин в образ вершины входят и , соответственно, , , . Теперь помечены все вершины, кроме , которая входит в образ вершины , то есть , работа алгоритма закончена. Минимальный путь (5 шагов) из вершины в вершину : .

Пусть – нагруженный ориентированный граф, , . Введем величины , где , . Для каждого фиксированного и величина равна длине минимального пути среди путей из в содержащих не более дуг. Если путей нет, то . Положим также для остальных . Составляем матрицу длин дуг порядка :

Утверждение. При , выполняется равенство

.