3.7. Задачи о минимальных расстояниях

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

1. Длина должна быть аддитивна (длина совокупности ребер или дуг равна сумме длин отдельных ребер или дуг).

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

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

Рассмотрим задачу нахождения кратчайшего пути между двумя заданными вершинами в

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

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

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

Деревом кратчайших расстояний относительно исходной вершины называется ориентированное дерево с корнем в такое, что путь (единственный) из до каждой вершины дерева является на самом деле кратчайшим путем

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

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

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

Доказательство. Если для некоторой хорды то путь по дереву из до вместе с хордой имеет длину Так как эта длина меньше чем то длина пути до по дереву не является, очевидно, минимальной.

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

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

Теорема доказана:

Теорема 3.25 дает теоретическую основу для итеративной процедуры, которая фактически будет давать

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

1. Возьмем в качестве любое дерево с корнем в включающее в себя все вершины, достижимые из

2. Обозначим расстояние от до в дереве полученном на шаге через Если каждая хорда удовлетворяет условию

то по теореме 3.25 Т есть максимальное дерево кратчайших расстояний. Если условие не выполняется, то пусть ( хорда такая, что

Пусть граф, получаемый из добавлением дуги (и, ну и вычеркиванием дуги, конечной вершиной которой является Из условия, что есть растущее дерево с корнем и что О для любого контура, получаем, что также является растущим деревом с корнем (Это утверждение предлагается доказать читателю в качестве упражнения.) Далее шаг 2 повторяется с предварительной заменой индекса на

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

В результате на некотором шаге итеративной процедуры получим

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

Пример. Предложенный метод нахождения дерева кратчайших расстояний иллюстрируется на рис. 3.32. В данном случае является исходной вершиной. Длины дуг заданы рис. 3.32, а. Сплошные дуги на рис. 3.32, b

соответствуют начальному дереву с корнем в которое покрывает граф. Здесь же показаны значения Пунктирная дуга является «улучшающей» хордой (т. е.

Рис. 3.32. (см. скан)

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

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

Полагая для всех мы можем найти пути, которые являются кратчайшими в том смысле, что они содержат наименьшее число дуг. В настоящее время разработано множество методов для нахождения деревьев кратчайших расстоянии в ориентированных графах. В работе [10] проводится сравнение нескольких алгоритмов. Алгоритм, рассмотренный выше, основан на методе «пометок» или «уменьшении индексов», который описан в работах [5] и [6].

Упражнения

(см. скан)

Можно предложить другой алгоритм для нахождения кратчайших путей в ориентированном графе, который основан на методе динамического программирования [1]. Рассмотрим ориентированный граф, показанный на рис. 3.34. (Предполагается, что все дуги ориентированы слева направо, но для простоты стрелки опущены.) Число у каждой дуги должно интерпретироваться как ее длина, и задача состоит в нахождении кратчайшего пути из любой вершины х (отличной от ну) к вершине

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

Рис. 3.34.

Поставим в соответствие каждой вершине х, удаленной от на одну дугу, дугу (в нашем случае единственную), содержащую х в качестве начальной вершины. Вершине х соответствует расстояние которое равно длине этой дуги. В нашем примере это расстояние равно 2 (для верхней вершины) и 1 (для нижней).

Рис. 3.35.

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

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

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

(см. скан)

ЛИТЕРАТУРА

(см. скан)