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

Известно [7, 15], что для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

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

Обозначим lj - длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

Шаг 0: Помечаем нулевую вершину индексом 10 = 0;

Шаг k: помечаем вершину k индексом 1k = min (1 + lik).

i< k

Индекс выхода 1n будет равен длине кратчайшего пути1. На рисунке 2 приведен пример применения алгоритма 1 для определения кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).

Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь m = (0; ii; i2; ¦¦¦; in-i; n), такой, что lin_n = 1n- ln-1 и т.д.

Рис. 2¦ Поиск кратчайшего пути

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом 10 = 0, все остальные вершины индексами 1i = +? i = 1,n ;

Шаг k: Рассматриваем все дуги.

Индексы устанавливаются за конечное число шагов. Обозна-

л *

чим { li } - установившиеся значения индексов, которые обладают

следующим свойством: величина 1* равна длине кратчайшего

пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

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

Шаг 0: Помечаем нулевую вершину индексом 10 = 0; Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q - множество непомеченных вершин, смежных с помеченными. Для каждой вершины k е Q вычисляем величину Xk = min (1k + lki), где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина Xk минимальна, индексом 1k = Xk.

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

Запишем задачу о кратчайшем пути как задачу линейного про-граммирования (ЛП). Пусть xij = 0, если дуга (i; j) входит в путь m,

xij = 0, если дуга (i; j) не входит в путь m, i, j = 0,n .

Задачу о минимальном пути можно записать в виде :

n

(1) Цх) = ^ljXj ® min

i, j=0 X

(2) Z Х0 j = 1, Z Xjn = 1

jj

Z x« = Z xjk, k = 1n -1.

ij

Любое решение системы неравенств (2)-(3) определяет путь в сети без контуров (но не в сети с контурами).

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

Сформулируем задачу ЛП, двойственную задаче (1)-(3), поставив в соответствие ограничениям (2) двойственные переменные 10 и 1n, а ограничениям (3) - двойственные переменные {1}, i = 1,n -1:

1n - 10 ® max

1j - 1 ?ljj, i, j = 0,n .

По теореме двойственности линейного программирования [7], для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых функций совпадают.

Задача (4)-(5) называется задачей о потенциалах вершин графа.

Ф(А) = Z \1j - 1j I, где {1° } могут интерпретироваться как

j

желательные потенциалы.

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

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

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

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

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

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

.