Кратчайшие пути в графе

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

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

Новые метки вычисляются для вершин по формуле:

L^H(x_j)=min {L^C(x_i); R_ij+L^*(x_i)}, (2.1)

где L^C(x_i) – старая временная метка вершины x_i;

L^H(x_j) – ее новая временная метка;

R_ij – вес ребра, соединяющего вершины x_j и x_j;

L^*(x_i) – постоянная метка вершины x_i.

Перед первой итерацией начальная вершина имеет постоянную метку l(x₁)=0, у остальных вершин пометки временные и полагаются равными ∞.

Итерация алгоритма состоит в просмотре всех вершин x с временными метками, к которым ведут дуги из вершины x_i – т.е. вершины, которая получила последней постоянную метку (для первой итерации x_i= x₁).

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

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

Пример. Для графа представленного на рис. 2.3, используя алгоритм Дейкстры, найти длины кратчайших путей от вершины 1 до остальных вершин, построить остовное дерево кратчайших путей.

Решать задачу будем, согласно алгоритму, итерационными процедурами. Результаты вычислений представим в таблице 2.9, и на рисунке 2.10.

Нулевая итерация. Зададим начальные условия - вершина x₁ имеет постоянную метку L^*(1 =0, а остальные вершины – метку ∞. Запишем эти данные в таблицу 2.2.

Рис. 2.3

Первая итерация. Вычислим расстояния от вершины 1 с постоянной меткой 0. Для этого запишем множество вершин связанных с вершиной 1 ребрами. Это множество последователей вершины 1:. F (1)={2, 3, 4, 6} и эти вершины имеют временные метки. Поэтому найдем для них новые временные метки согласно формуле (2.1).

L^H(2)=min {L^C(2); R₁₂+L^*(1)}=min{∞;6+0}=6;

L^H(3)=min {L^C(3); R₁₃+L^*(1)}=min{∞;4+0}=4;

L^H(5)=min {L^C(5); R₁₅+L^*(1)}=min{∞;6+0}=6;

L^H(6)=min {L^C(6); R₁₆+L^*(1)}=min{∞;8+0}=8.

Остальные вершины имеют прежние метки - ∞. Запишем это в строку итерации 1 в таблице 2.3.

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

min L(j)=min{L(2), L(3), L(4), L(5), L(6), L(7), L(8)}= min{6, 4, ∞, 6, 8, ∞}=4.

Наименьшее значение 4 достигается на метки 3. Поэтому это значение в таблице выделим.

Приступим к построению дерева минимальных путей, которое будем строить последовательно, итерацией за итерацией. Процесс построения дерева представлен рисунками *.1 - *. х. Первая итерация дала постоянную метку вершине 3, как последователю вершины 1. В дереве кратчайших путей это соответствует появлению ребра, соединяющего вершины 1 и 3. На рис. 2.4 изображены все вершины графа, так как искомое дерево остовное, это значит, что вершины должны совпадать с вершинами исходного графа. Проведем первое найденное ребро, соединяющее вершины 1 и 3.

Рис. 2.4

Вторая итерация. Определим множество последователей вершины 3: F(3)={1, 2, 4, 5, 7, 8}. Вершина 1 уже имеет постоянную метку, поэтому новые метки найдем для вершин 2, 4, 5, 7, 8.

L^H(2)=min {L^C(2); R₃₂+L^*(3)}=min{6;4+4}=6;

L^H(4)=min {L^C(4); R₃₄+L^*(3)}=min{ ∞; 13+4 }=17;

L^H(5)=min {L^C(5); R₃₅+L^*(3)}=min{6;5+4}=6;

L^H(7)=min {L^C(7); R₃₇+L^*(3)}=min{∞;18+4}=22;

L^H(8)=min {L^C(8); R₃₈+L^*(3)}=min{∞;25+4}=29.

Замечаем, что для вершин 2 и 5 метки остались прежними, поэтому не заносим их в строку второй итерации таблицы 2.4, остальные обновления заносим в клетки строки. Среди всех вершин имеющих временные пометки, ищем вершину с наименьшим значением:

min L(j)= min{L(2), L(4), L(5), L(6), L(7), L(8)} = min{6, 17, 6, 8, 22, 29}=6.

Минимальную метку имеют две вершины 2 и 6, поэтому постоянную метку можно присвоить любой из этих вершин. Например, присвоим постоянную метку вершине 2: L^*(2)=6.

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

Рис. 2.5

Третья итерация. Множество последователей вершины 2: F(2)={1, 3, 4}. Среди этих вершин только 4 имеет временную метку. Переопределим ее:

L^H(4)=min {L^C(4); R₂₄+L^*(2)}=min{17;13+6}=17.

Выберем новую постоянную метку.

min L (j)= min{L(4), L(5),L (6),L(7), L(8)}=min{17, 6, 8, 22, 29}=6.

Таким образом, вершина 5 получает постоянную пометку: L^*(5)=6.

Заполняем столбец третьей итерации в табл. 2.5 (поскольку единственная найденная новая метка совпадает со старой, в строке указываем только вершину, которая получила постоянную метку). А в дерево кратчайших путей добавляем ребро, соединяющее вершины 1 и 5 (см. рис. 2.6).

Рис. 2.6

Четвертая итерация. F(5)={1, 3, 6, 7}. Находим новые метки для вершин6 и 7, так как вершины 1 и 3 уже имеют постоянные.

L^H(6)=min {L^C(6); R₅₆+L^*(5)}=min{8;5+6}=8;

L^H(7)=min {L^C(7); R₅₇+L^*(5)}=min{22;10+6}=16.

Заполняем строку итерации 4 в таблице *. 5: метка для вершины 6 не изменилась, поэтому заносим только метку для 7 вершины.

Выберем теперь постоянную метку: min L (j)= min{ L (4), L (6), L (7), L (8)} = min{ 17, 8, 16, 29}=8. Следовательно, L^*(6)=8.

В дерево добавляется ребро, соединяющее вершины 1 и 6 (рис. 2.7).

Пятая итерация. Множество последователей вершины 6: F(6)={1, 5, 7}. Среди этих вершин только 7 вершина имеет временную метку. Переопределим ее:

L^H(7)=min {L^C(7); R₆₇+L^*(6)}=min{16;12+8}=16. Метка не изменилась, поэтому в строку 5 итерации таблицы 2.7 занесем новую постоянную пометку, которую выберем как

min L(j)=min{L(4), L(7), L(8)=min{17, 16, 29}=16.

Рис. 2.7

Вершина 7 получает постоянную метку L^*(7)=16, а дерево ребро, соединяющее вершины 5 и 7 (см. рис. 2.8).

Рис. 2.8

Шестая итерация. Определим множество последователей вершины 7 - F(7)={3, 5, 6, 8}. Находим новые метки для 8 вершины:

L^H(8)=min {L^C(8); R₇₈+L^*(7)}=min{29;12+16}=28.

Остальные вершины уже имеют постоянные пометки, поэтому заполняем строку 6 итерации (табл. 2.8) и выбираем постоянную пометку.

min L(j)=min{L(4), L(8)}=min{17,28}=17.

Следовательно, L^*(4)=17.

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

Рис. 2.9

Седьмая итерация. F(4)={2, 3, 8}. Все вершины, кроме 8, имеют постоянные метки, поэтому для нее находим новую временную метку:

L^H(8)=min {L^C(8); R₄₈+L^*(4)}=min{28; 10+17}=28.

Следовательно, L^*(8)=28. Заносим результат в таблицу 2.9, которая и будет окончательной таблицей решения задачи.

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

Замечание. При выполнении соответствующего задания нет необходимости заполнять таблицы 2.2 – 2.9 и рисовать рис. 2.3 – 2.10. Достаточно последовательно заполнять одну таблицу и одновременно рисовать рисунок.

Рис. 2.10

Задача сетевого планирования и управления PERT

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

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

Считается, что время выполнения этапа – это вес дуги .

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

Алгоритм и его реализацию рассмотрим на примере решения задачи.

Пример. Граф, изображенный на рисунке 2.11, описывает некоторый проект. Дуги графа u_iu_j соответствуют этапам проекта, а вес дуги обозначает время t(u_iu_j) выполнения этапа. Найти наименьшее время выполнения проекта, критические пути и резерв времени для выполнения операции u_i®u_j.

Рис. 2.11

Решение задачи разобьем на этапы.

Этап 1. Найдем наибольшее время l(u_j) начала операции, соответствующие дугам, исходящим из вершины u_i, где i=1, 2,…, n, j>i, по формуле 2.2:

(2.2)

При этом считаем, что l(u₁)=0 – начальное условие алгоритма.

l(u₂)= l(u₁)+t(u₁u₂)=0+3=3;

l(u₃)= max(l(u₁)+t(u₁u₃); l(u₂)+t(u₂u₃))= max(0+3;3+3)=6;

l(u₄)= max(l(u₁)+t(u₁u₄); l(u₂)+t(u₂u₄))= max(0+4;3+2)=5;

l(u₅)= max(l(u₂)+t(u₂u₅); l(u₄)+t(u₄u₅))= max(3+2;5+3)=8;

l(u₆)= max(l(u₄)+t(u₄u₆); l(u₅)+t(u₅u₆))= max(5+5;8+2)=10;

l(u₇)= l(u₃)+t(u₃u₇)= 6+4=10;

l(u₈)= max(l(u₅)+t(u₅u₈); l(u₆)+t(u₆u₈); l(u₇)+t(u₇u₈))= max(8+4;10+3; 10+2)= 13.

Результаты вычислений запишем во вторую строку таблицы 2.10. По результатам вычислений пучили, что минимальное время выполнения проекта равно l(u₈)=13.

Этап 2. Теперь определим критические пути, т.е. наибольшие пути от начальной вершины графа к конечной. Как видно из 1 этапа таких путей 2:

1 путь - u₁®u₂®u₄®u₆®u₈;

2 путь - u₁®u₂®u₄®u₅®u₆®u₈.

Этап 3. Найдем самое позднее время начала операций L(u_i), отвечающих дугам, исходящим из вершины u_i, при котором весь проект все еще может быть выполнен за минимальное время. Для этого:

а) поменяем ориентацию каждой дуги (рис. 2.12), при этом поменяются местами начальная и конечная вершины, т.е. u₈ станет начальной вершиной графа, а u₁ – конечной;

Рис. 2.12

б) найдем самый длинный путь l¢(u_j) от вершины u₈ до вершины u₁, используя алгоритм 1 этапа:

l¢(u₈)=0 – начальное условие;

l¢(u₇)= l¢(u₈)+t(u₈u₇)= 0+2=2;

l¢(u₆)= l¢(u₈)+t(u₈u₆)= 0+3=3;

………………………………….;

l(u₁)= max(l¢(u₂)+t(u₂u₁); l¢(u₃)+t(u₃u₁); l¢(u₄)+t(u₄u₁))= max(10+3;6+3; 8+4)= 13.

Результаты вычислений заносим в третью строку таблицы 2.10.

в) вычислим самое позднее время начала операций по формуле 2.3:

L(u_j)= l(u₈)- l¢(u_j) (2.3)

Результаты вычислений записаны в последней строке таблицы 2.10.

Этап 4. И, наконец, определим резерв времени r(u_iu_j) для каждой операции проекта по формуле 2.4:

r(u_iu_j)= L(u_j)- l(u_j)- t(u_iu_j) (2.4)

Например, посчитаем резерв времени для дуги (u₃u₇), не входящей в критический путь. Он будет равен:

r(u₃u₇)= L(u₇)- l(u₃)- t(u₃u₇)=11-6-4=1.

Таким образом, получили, что операция, соответствующая дуге (u₃u₇) может начать выполняться с задержкой на 1 единицу времени и это не повлияет на общее время выполнения проекта. Аналогично можно найти резерв времени и для других операций проекта, не входящих в критический путь.

Потоки в сетях

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

Вес дуги означает ее пропускную способность.

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

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

Поток называется полным, если он содержит одну насыщенную дугу.

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

Величина потока (или максимальный поток сети) W - сумма потоков по дугам, исходящим из источника. Или же это сумма потоков входящих в сток.

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

Для решения такого рода задач используется алгоритм Форда-Фелкерсона. Алгоритм состоит из трех частей – насыщение потока, его перераспределение и определение максимального потока сети.

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

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

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

Пример. Задана пропускная способность дуг транспортной сети (рис. 2.13) с началом в вершине 1 и концом в вершине 8. Используя алгоритм Форда-Фелкерсона, найти максимальный поток по сети.

Рис. 2.13

Решение начинаем с первого этапа – насыщение потока. Для начала пропустим через всю сеть поток, равный 0. В числителе ставим пропускную способность, а в знаменателе - поток. При этом числитель всегда больше знаменателя, а знаменатель может быть и нулем (рис. 2.14).

Рис. 2.14

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

Рассмотрим путь 1-2-4-6-8. Пропустим через этот путь поток, равный 4 (так как 4 – наименьшая пропускная способность, встречающаяся на рассматриваемом пути). При этом дуги [2, 4] и [4, 6] будут насыщенными. Аналогично, путь 1-3-5-7-8 насытим потоком 4. Дуга [7, 8] будет насыщенной. Распределение потока отметим на графе (рис. 2.15, жирными линиями выделены рассматриваемые пути).

Из вершины 1 в вершину 8 есть еще один путь 1-3-2-5-4-7-6-8, поток в котором можно увеличить на 2. При этом насытятся дуги [1, 3], [2, 5] и [4, 7] (рис. 2.16).

Рис. 2.15

Из 1 в 8 больше нет ненасыщенных путей. Так как по дуге [1, 3] двигаться нельзя - она уже насыщена, а движение по дуге [1, 2] заканчивается в вершине 2 – обе выходящие из нее дуги насыщены. Поэтому первый этап решения задачи считаем решенным.

Рис. 2.16

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

Рис. 2.17

В нашем графе есть единственная такая последовательность: 1-2-3-5-7-6-8 (рис. 2.17). Перераспределяем поток. Для этого поток в дугах прямого назначения увеличиваем на 1, а поток в дугах обратного направления уменьшаем на 1. Процесс продолжаем до тех пор, пока одна из прямых дуг не будет насыщена или какая-нибудь обратная дуга не будет пуста. В данном примере процесс заканчиваем на первом шаге перераспределения, так как дуга [6, 8] стала насыщенной (см. рис. 2.18).

3 этап – нахождение максимального потока по сети. Поток в насыщенной сети можно посчитать по потоку, выходящему из истока 1 или входящему в сток 8. Очевидно, эти числа должны быть равны. Кроме того, для проверки решения следует проверить условие сохранения потока по узлам. Для каждого узла суммарный входящий поток должен быть равен выходящему.

Рис. 2.18

Проверим условие сохранения потока. Возьмем произвольную вершину, например 5. В нее входят дуги [2, 5] и [3, 5] с потоками 2 и 5 соответственно, поэтому их суммарный поток будет равен 2+5=7. Суммарный выходящий поток посчитаем сложением потоков дуг [5, 4] и [5, 7], он равен тоже 7. Поэтому делаем вывод, что задача решена верна.

Теперь найдем максимальный поток сети. Для истока сети 1 он равен W(1)=5+6=11, т.е. сумме потоков дуг [1, 2] и [1, 3]). Для стока 8 поток сети получаем сложением потоков дуг [6, 8] и [7, 8]: W(8)=7+4=11.

В результате решения задачи получили, что поток равен 11.

Не нашли, что искали? Воспользуйтесь поиском: