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

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

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

Пусть задана сеть из n+1 вершины, то есть ориентированный граф, в котором выделены две вершины - вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.

Теорема 1 [8]. Для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

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

Известно, что в сети без контуров всегда существует правильная нумерация.

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

Алгоритм 1.

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

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

Индекс выхода l_n будет равен длине кратчайшего пути.

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

Шаг 0. Вершине 0 присваиваем индекс равный 0.

Шаг 1. Рассматриваем вершину 1. Индекс вершины равен

λ₁ =min(λ₀ +l₀₁)=0+3=3

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

Шаг 2. Рассматриваем вершину 1. Индекс вершины равен

λ₁ =min(λ₀+l₀₁)=0+3=3

Шаг 3. Рассматриваем вершину 3. Индекс вершины равен

λ₃ =min(λ₁+l₁₃; λ₂+l₂₃)=min(3+8;8+2)=10

Шаг 4. Рассматриваем вершину 4. Индекс вершины равен

λ₄ =min(λ₂ +l₂₄)=8+1=9

Шаг 5. Рассматриваем вершину 5. Индекс вершины равен

λ₅ =min(λ₃ +l₃₅; λ₄ +l₄₅)=min(10+4;9+6)=14

Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь m = (0; i₁; i₂; ...; i_n-1; n), такой, что = l_n - l_n-1 и т.д.

Осуществляя обратный ход для рассматриваемого примера получаем:

λ₅= λ₃+l₃₅;

λ₃= λ₂+l₂₃;

λ₂= λ₁+l₁₂;

λ₁= λ₀+l₀₁;

Таким образом, кратчайший путь проходит через вершины:

0→1→2→3→5

и имеет длину равную 14.

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

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

Шаг 0: Помечаем нулевую вершину индексом l₀ = 0, все остальные вершины индексами l_i = +¥, i = ;

Шаг k: Рассматриваем все дуги. Для дуги (i; j), если l_j - l_i >l_ij, то вычисляем новое значение = l_i + l_ij.

Индексы устанавливаются за конечное число шагов. Обозначим { } – установившиеся значения индексов, которые обладают следующим свойством: величина равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

Пример. Рассмотрим пример работы алгоритма Форда для сети с произвольной нумерацией вершин для сети изображенной на рис. 13.

Рис. 13. Поиск кратчайшего пути для алгоритма Форда

Шаг 0. λ₀=0; λ₁=∞; λ₂=∞; λ₃=∞; λ₄=∞; λ₅=∞.

Шаг 1. Рассматриваем дугу (0;1). Вычисляем соотношение λ₁ – λ₀=∞. Проверяем выполнение условия (λ₁ – λ₀)>l₀₁. Соотношение выполняется, поэтому вычисляем новое значение λ₁

λ₁=(λ₀ +l₀₁)=0+3=3

Шаг 2. Рассматриваем дугу (0;2). Вычисляем соотношение λ₂ – λ₀=∞. Проверяем выполнение условия (λ₂ – λ₀)>l₀₁. Соотношение выполняется, поэтому вычисляем новое значение λ₂: λ₂=(λ₀ +l₀₂)=0+9=9

Шаг 3. Рассматриваем дугу (1;3). Вычисляем соотношение λ₃ – λ₁=∞. Проверяем выполнение условия (λ₃ – λ₁)>l₁₃. Соотношение выполняется, поэтому вычисляем новое значение λ₃: λ₃=(λ₁ +l₁₃)=3+8=11

Шаг 4. Рассматриваем дугу (3;2). Вычисляем соотношение λ₂ – λ₃=9 – 11= - 3 . Проверяем выполнение условия (λ₂ – λ₃)>l₃₂. Соотношение не выполняется, поэтому новое значение λ₂ не вычисляется.

Шаг 5. Рассматриваем дугу (2;1). Вычисляем соотношение λ₁ – λ₂=3 – 9= - 6. Проверяем выполнение условия (λ₁ – λ₂)>l₂₁. Соотношение не выполняется, поэтому новое значение λ₁ не вычисляется.

Шаг 6. Рассматриваем дугу (2;4). Вычисляем соотношение λ₄ – λ₂=∞. Проверяем выполнение условия (λ₄ – λ₂)>l₂₄. Соотношение выполняется, поэтому вычисляем новое значение λ₄: λ₄=(λ₂ +l₂₄)=9+1=10

Шаг 7. Рассматриваем дугу (3;5). Вычисляем соотношение λ₅ – λ₃=∞. Проверяем выполнение условия (λ₅ – λ₃)>l₃₅. Соотношение выполняется, поэтому вычисляем новое значение λ₅: λ₅=(λ₃ +l₃₅)=11+4=15

Шаг 8. Рассматриваем дугу (4;5). Вычисляем соотношение λ₅ –λ₄=15 – 10 =5. Проверяем выполнение условия (λ₅ – λ₃)>l₀₁. Соотношение не выполняется, поэтому новое значение λ₅ не вычисляется.

Обратным ходом получаем кратчайший путь 5→3→1→0

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

Алгоритм 3 (алгоритм Данцига).

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

Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q – множество непомеченных вершин, смежных с помеченными. Для каждой вершины k Î Q вычисляем величину x_k = min (l_k + l_ki), где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина x_k минимальна, индексом l_k = x_k.

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

Пример алгоритма Данцига

Позволяет найти кратчайший путь между некоторой вершиной s и остальными вершинами при условии, что в графе нет дуг (ребер) с отрицательным весом. Рассмотрим основную идею алгоритма на примере графа на рис. 1 с матрицей смежности С. Пустые клетки означают, что соответствующих дуг в графе нет. Можно считать также, что дуги есть и каждая имеет вес равный ∞). В качестве начальной возьмем вершину v₅.

	v1	v	v3	v4	v5	v6	v7	v8	v9	v10
v1

v2
v3
v4
v5
v6
v7
v8
v9
v10

Выделим все вершины смежные рассматриваемой, то есть вершине v₅и припишем им числовые метки l(v_i), равные весам дуг (v₅,vi), как показано на рис. 2 (веса проставлены около дуг, а метки - около вершин и заключены в круглые скобки). Очевидно, что кратчайший путь до v₂состоит из един­ственной дуги (v₅,v₂), а его длина l(v₂)=5.

Рис. 2

Зафиксируем эту вершину и будем считать ее метку постоянной. Таким образом, для v₂ задача решена. Относительно остальных четырех вершин можно лишь утверждать, что длины кратчайших путей до них не превосходят значений l(vi). Поэтому соответствую­щие метки пока считаем временными. В дальнейшем, чтобы различать постоянные и временные метки постоянные будем заключать в рамку.

Выделим все вершины смежные v₂. Таких четыре v₁, v₃, v₄, v₆и рассмотрим дуги (v₂, v_i)изображенные на рис. 3. Поскольку l(v₂)+c(v₂, v₃)<l(v₃),"обходной" путь v₅→v₂→v₃ короче чем «прямой»

.

Рис. 3

(v₅ → v₃), поэтому за новое значение метки l(v₃) примем сумму

l(v₂)+c(v₂,v₃)=12.

Аналогичной проверкой устанавливаем, что прямой путь (v₅ → v₄) короче, чем обходной v₅→v₂→v₄, следовательно значение метки l(v₄) сохраняется прежним. Для вершины v₆, как и для v₃, метка корректируется и принимает значение 27. Кроме вершин v₃, v₄ и v₆, достижимых из v₅ не­посредственно, есть еще одна вершина v₁, единственный путь к которой лежит через постоянно помеченную v₂. Поэтому в качестве значения метки для нее естественно вять сумму l(v₂)+c(v2,v1). Будем говорить что теперь метки l(v₁),l(v₃) и l(v₆) получены из вершины v₂. Из пяти временных меток минимальной является l(v₃)=12, которая и определяет длину кратчайшего пути до v₃. Так как метка получена из v₂, путь имеет вид v₅→v₂→v₃. Таким образом, задача решена идля v₃, которая становится постоянно помеченной. Этот факт отражен на рис. 4.

Рис. 4

Кроме уже рассмотренных дуг, изображена и единственная дуга, выходящая из v₃. Наличие этой дуги требует пересчета значения метки l(v₆). Так как l(v₃)+c(v₃, v₆)<27, за новое значение l(v₆)примем сумму l(v₃)+c(v3, v₆)=25. Минимальной среди временных меток является l(v1)=15. Это значит, что выявлен кратчайший путь v5→v2→v₁, а метка вершины v₁ становится постоянной. Последующие действия выполня­ются аналогично. Для v₁, как последней постоянно помечен­ной находим множество смежных еще непомеченных вершин v₄, v₅, v₇и анализи­руем их метки, принимая во внимание длины дуг, связывающих v₁ с этими вершинами. Так как l(v₁)+c(v₁, v₄)<l(v₄), метка вершины v₄ корректи­руется, становясь равной 18.

Рис. 5

У вершины v₅ метка посто­янная и поэтому не меня­ется. Наконец, v₇, до этого не рассматривавшаяся, полу­чает начальную метку равную l(v₁)+c(v₁, v₇)=25. Граф, отра­жающий ситуацию, представ лен на рис. 5. Здесь минимальной временной меткой оказывается d(v₄)=18. Теперь вершина v₄ становится постоянно помеченной. Так как вою метку она получила из v₁, кратчайший путь к ней со стоит из кратчайшего пути до v₁ и дуги (v₁, v₄) и выглядит так v₅→v₂→v₁→v₄, а его длина равна 18.

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

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

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

Таблица 2

Итерация

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

p

l(p)

1

v5

0

v2

v3

v1

v4

6

25

23

v8

21

v7

v6

v9

v10

пред

v2

v5

v2

vч

v5

vз

v

v

vб

vб

На первой итерации полагаем временные метки для всех вершин, кроме начальной, равными ∞, а для начальной – 0. Последней постоянно помеченной считаем вершину v₅, а, е метку равной 0.

На второй итерации, используя матрицу С, находим все вершины смежные с вершиной v₅ и перечитываем их временные мет­ки по формуле l(vi)=min{l(vi), l(v_p)+c(vp, vi)}. Среди времен­ных меток ищем минимальную. Это метка вершины v₂, теперь ее считаем постоянно помеченной.

На третьей итерации находим вершины смежные с v₂ и пересчитываем их временные метки. Среди всех временных вновь ищем минимальную метку. На этой итерации постоянно помеченной становится вершина v₃, и т.д.

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

Чтобы находить сами пути, сформируем еще одну строч­ку таблицы (пред), в которой для каждой вершины графа указана ее предшественница на кратчайшем пути. С этой целью в каждом столбце отыскиваем самую нижнюю строку с предпоследним значением метки. Например, в первом столбце это вторая строка, в восьмом - пятая. Искомая вершина-предшественница содержится в столбце p найденной стро­ки. Для v₁ это вершина v₂, а для v₈ - вершина v₄. Теперь для определения самого пути достаточно записать цепочку вершин-предшественниц начиная с конечной вершины. Так для v₁₀ имеем: v₆, v₃, v₂, v₅. Это значит, что кратчайший путь между v₅ v₁₀ имеет вид v₅v₂v₃v₆v₁₀ .