1.1 Алгоритм поиска кратчайшего пути

Каждой дуге (х,у) исходного графа G поставим в соответствие число а(х,у). Если в графе G отсутствует некоторая дуга (x, y), положим a(x, y)=∞. Будем называть число а(х, у) длиной дуги (х, у), хотя а(х, у) можно также интерпретировать как соответствующие за­траты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

Для любых двух вершин s и t графа G могут существовать не­сколько путей, соединяющих вершину s с вершиной t. В данном разделе будет рассмотрен алгоритм, который определяет такой путь, ведущий из вершины s в вершину t, который имеет минималь­но возможную длину. Этот путь называется кратчайшим путем между вершинами с и t.

Пример 1. Предположим, что вы хотите проехать из Бостона в Лос-Анджелес, используя магистральные шоссейные дороги, соединяющие различные штаты. Как выбрать кратчайший маршрут?

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

Пример 2. Пассажир обращается за услугами к некоторой авиакомпании. Он желает попасть воздушным путем из Спрингфилда (шт. Иллинойс) в столицу Турции Анкару, проведя в воздухе как можно меньше времени, поскольку полет на самолете вызывает у него чувство страха. Какой маршрут в данном случае должна предложить авиакомпания пассажиру?

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

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

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

Пример 4. Представим себе следующую ситуацию. Коммивояжер планирует поездку из Бостона в Лос-Анджелес. Цель поездки — посеще­ние одного из основных клиентов. Коммивояжер собирается воспользовать­ся той же системой магистральных шоссейных дорог, которая фигурировала в примере 1. Помимо основной цели поездки коммивояжер планирует посе­щение и других пунктов, расположенных на пути из Бостона в Лос-Андже­лес, где размещаются другие его клиенты. При этом коммивояжер прибли­зительно знает, какую сумму комиссионных он заработает после возможной встречи с каждым из клиентов. Какой маршрут поездки из Бостона в Лос-Анджелес следует выбрать коммивояжеру?

В рассматриваемом случае длиной каждой дуги в графе, представляю­щем рассматриваемую систему магистральных шоссейных дорог, следует считать ожидаемую «чистую стоимость» проезда (транспортные затраты за вычетом ожидаемой суммы комиссионных) по определенному участку дан­ной системы дорог. Теперь можно сказать, что коммивояжер должен ехать по маршруту, соответствующему кратчайшему пути в построенном графе между вершинами «Бостон» и «Лос-Анджелес».

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

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

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

Главная идея, лежащая в основе алгоритма Дейкстры, предель­но проста. Предположим, что нам известны т вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в х). Пусть также извест­ны сами кратчайшие пути, соединяющие вершину s с выделенны­ми т вершинами ( кратчайшим путем из s в х считается нулевой путь, не содержащий дуг. Длина этого пути, естественно, принимается равной нулю ). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.

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

Какая же из неокрашенных вершин является (m+1)-й бли­жайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчай­ший путь из вершины s в (т+1)-ю ближайшую вершину при по­ложительном значении длин всех дуг должен содержать в каче­стве промежуточных лишь окрашенные вершины, т.е. вершины, входящие в число т вершин, ближайших к вершине s.

Итак, если известны т ближайших к s вершин, то (т+ 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с т=0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.

Имея в виду приведенные соображения, мы можем теперь фор­мально описать алгоритм Дейкстры.

Алгоритм Дейкстры поиска кратчайшего пути

Шаг 1. Перед началом выполнения алгоритма все вершины и дуги не окрашены. Каждой вершине в ходе выполнения алгоритма присваивается число d(x), равное длине кратчайшего пути из s в х, включающего только окрашенные вершины.

Положить идля всехх, отличных от s. Окра­сить вершину s и положить (у — последняя из окрашенных вершин).

Шаг 2. Для каждой неокрашенной вершины х следующим об­разом пересчитать величину d(x):

(1)

Если для всех неокрашенных вершин х, закончить процедуру алгоритма: в исходном графе отсутствуют пути из вер­шины s в неокрашенные вершины. В противном случае окрасить ту из вершин х, для которой величина d(x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину х (для этой дуги достигался минимум в соответствии с выражением (1)). Положить 𝒚.

Шаг 3. Если , закончить процедуру; кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

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

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

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

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

Пример 6. Применим алгоритм Дейкстры к графу, изображенному на рис. 3.1, для нахождения в нем кратчайшего пути между вершинами s и t.

Перед первым выполнением шага 2 алгоритма окрашена только вер­шина s. Кроме того, и для всех вершин х, не совпадаю­щих с s.

Шаг 2.

Поскольку величина является минимальной из величинd(a), d(b), d(d), d(i) и d(t), то вершина c окрашивается. Так же окрашивается и дуга (s, с), которая и определяет величину d(c). Текущее дерево кратчайших путей состоит из дуги s, с (рис. 3.2, а).

Шаг 3, Поскольку вершина t остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2.

Поскольку величина d(a) = 4 является минимальной из величия d(a), d(b),d(d) и d(t), то вершина а окрашивается. Так же окрашивается и дуга (s,а), которая определяет величину d(a). Текущее дерево кратчайших путей теперь состоит из дуг (s, с) и (s, а) (рис. 3.2, б).

Шаг 3. Поскольку вершина t остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2.

Поскольку величина d(d) = 6 является минимальной из величин d(b),d(d) и d(t), то вершина d окрашивается. Можно считать, что величину d(d) определяют как дуга (с, d), так и дуга (a, d). Поэтому можно окрасить любую из этих дуг. Окрасим, например, дугу (с, d). Текущее дерево крат­чайших путей состоит теперь из дуг (s, с), (s, а) и (s, d) (рис. 3.2, в).

Шаг 3. Поскольку вершина t остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2.

Поскольку величина меньше величиныd(t) то вершина 6 окрашивается. Так же окрашивается и дуга (s, b), которая определяет величину d(b). Текущее дерево кратчайших путей теперь со­стоит из дуг (s, с), (s, а), (с, d) и (s, b) (рис. 3.2, г).

Шаг 3. Поскольку вершина t остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2.

Итак, вершина t наконец-то окрашивается. Вместе с нею окрашивается дуга (d, t), определяющая величину d(t). Окончательно построенное дерево крат­чайшие путей состоит из дуг (s, с), (s, а), (с, d), (s, b) и (d, t) (рис. 3.2, д).

Кратчайший путь, соединяющий вершину s с вершиной t, состоит из дуг (s, с), (c, d) и (d, t) и имеет длину 3+3+2=8. Это не единственный кратчайший путь между вершинами s и t. Путь, состоящий из дуг (s, а), (a, d) и (d, t), имеет длину 4 + 2+ 2 = 8 и также является кратчайшим путем между вершинами s и t. Кратчайший путь будет единственным в том случае, если в процедуре алгоритма ни разу не возникает неоднозначность в выборе окрашиваемой дуги.

Исходное предположение в алгоритме Дейкстры состояло в не отрицательности длин дуг исходного графа. К каким ре­зультатам приводил бы алгоритм Дей­кстры, если некоторые из длин дуг были бы отрицательными? Для примера рассмо­трим граф, изображенный на рис. 3.3. В этом графе кратчайшим путем, соединяю­щим вершины s и t, является путь, состоя­щий из дуг (s, а) и (a, t). Длина этого пу­ти равна 2-2 = 0. Читатель может легко убедиться в том, что алгоритм Дейкстры, будучи применен к графу, изображенному на рис. 3.3, ошибочно укажет в качестве кратчайшего путь, со­стоящий из дуги (s, t). Таким образом, нет никакой гарантии, что алгоритм Дейкстры будет находить кратчайший путь в слу­чаях, когда длины дуг могут быть отрицательными (как это, кстати, имеет место в примерах 4 и 5).

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

1. На шаге 2 алгоритма пересчет величин d(x) с помощью соотношения(1) производится для всех вершин, а не только для неокрашенных. Следовательно, числа d(x) могут уменьшаться как для неокрашенных, так и для окрашенных вершин.

2. Если для некоторой окрашенной вершины x происходит уменьшение величины d(x), то с этой вершины и инцидентной ей окрашенной дуги окраска снимается.

3. Процедура алгоритма заканчивается только тогда, когда все вершины окрашены и когда после выполнения шага 2 ни одно из чисел d(x) не меняется.

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

(2)

(Иначе с вершины y была бы обязательно снята окраска на итерации, непосредственно следующей за итерацией, на которой была окрашена вершина x).

Итак, предположим, что после окончания процедуры алгоритма Форда величина d(y) для некоторой вершины y не совпадает с длиной кратчайшего пути до этой вершины из вершины s (если в графе несколько таких вершин y, то выбирается та из них, кратчайший путь до которой из вершины s содержит наименьшее число дуг). Отметим, что если величина d(z) для произвольной вершины z конечна, то она представляет собой длину некоторого пути , соединяющего вершины s и z. Поэтому по окончании процедуры алгоритма величина d(y) должна совпадать с длиной некоторого пути из вершины s в вершину y, и в силу сделанного предположения эта величина должна превышать длину кратчайшего пути между указанными вершинами. Пусть вершина x является предпоследней вершиной кратчайшего пути между s и y. Если таких путей несколько, то в качестве x берется та вершина, кратчайший путь до которой от вершины s включает наименьшее число дуг. В силу выбора вершин x и y величина d(x) должна совпадать с длиной кратчайшего пути из s в x, откуда . Однако последнее соотношение противоречит соотношению (2). Полученное противоречие завершает обоснование алгоритма Форда.

Пример 7. Применим алгоритм Форда к графу, изображенному на рис. 3,3

Шаг 1. Окрашивается вершина s. Полагается , и

Шаг 2.

Поскольку d(t) меньше, чем d(a), вершина t окрашивается. Вместе с ней ок­рашивается дуга (s, t), которая и составляет текущее дерево кратчайших путей.

Шаг 3. Поскольку окрашены не все вершины, делается переход к шагу 2.

Шаг 2.

Поскольку из вершины t не исходит ни одной дуги, все числа d(x) ос­таются неизменными. Поэтому окрашивается вершина а и вместе с ней дуга (s, а). Теперь дерево кратчайших путей состоит из дуг (s, t) и (s, a).

Шаг 3. Осуществляется возврат к шагу 2 с тем, чтобы попытаться умень­шить числа d(x).

Шаг 2. Определяются:

Поскольку величина d(t) уменьшается от 1 до 0, с вершины t и дуги (s, t) снимается окраска. Теперь дерево кратчайших путей состоит только из

дуги (s, a).

В исходном графе остается неокрашенной только одна вершина — вер­шина t. Эта вершина окрашивается вместе с дугой (a, t), поскольку в ка­честве у на данном шаге фигурирует а. Дерево кратчайших путей теперь включает дуги (s, а) и (a, t).

Шаг 3. Осуществляется очередной возврат к шагу 2.

Шаг 2.

Поскольку из вершины t не исходит ни одной дуги, величины d(x) не меняются. Неокрашенных вершин в исходном графе нет.

Шаг 3. Поскольку все вершины графа оказываются окрашенными и на предыдущем шаге алгоритма ни одну из величин d(x) не удалось умень­шить, процедура алгоритма заканчивается. Кратчайший путь из вершины s в вершину t состоит из дуг (s, a), (a, t) и имеет длину 2—2 = 0.

Во всех ли случаях алгоритм Форда решает задачу нахождения кратчайшего пути? Оказывается, не во всех. Алгоритм Форда не решает указанной задачи при наличии в исходном графе контура, имеющего отрицательную длину. Действительно, в этом случае, неограниченное число раз «повторяя» этот контур, можно получить путь со сколь угодно малой по величине длиной. Для коммивоя­жера из примера 4 контур отрицательной длины соответствует «прибыльному» замкнутому маршруту, повторяя который неогра­ниченное число раз, коммивояжер может получить сколь угодно большую по величине прибыль. В примере 5 соответствующий граф вообще не имеет контуров, поэтому в этом случае алгоритм Форда может применяться вне всяких сомнений.

А что делать в ситуации, когда нет сведений об отсутствии или наличии в рассматриваемом графе контуров отрицательной длины?

В такой ситуации можно обычным образом применять алгоритм форда, но в процессе его работы необходимо учитывать, сколько раз окрашиваются отдельные вершины. Как только число окраши­ваний какой-либо вершины достигает величины N, где N — число вершин графа, процедуру алгоритма можно остановить: исходный граф содержит контур отрицательной длины. Если же этого не происходит, то процедура алгоритма Форда завершается за ко­нечное число шагов, правильно решая исходную задачу.

Для обоснования приведенного правила предположим, что исходный граф не содержит контуров отрицательной длины. Тогда если у некоторой вершины х величина d(x) приобретает окончатель­ное значение (т. е. определяется длина кратчайшего пути из s в x), то в худшем случае каждая из оставшихся вершин может быть окрашена вновь (или впервые) только один раз, прежде чем будет окончательно окрашена одна из них. Таким образом, ни одна вер­шина не может быть окрашена более (N — 1) раза.