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).
К счастью, алгоритм Дейкстры может быть обобщен на случай, когда некоторые из дуг имеют отрицательные длины. Идея соответствующего обобщения принадлежит Форду. Необходимая модификация алгоритма Дейкстры состоит в следующем:
На шаге 2 алгоритма пересчет величин d(x) с помощью соотношения(1) производится для всех вершин, а не только для неокрашенных. Следовательно, числа d(x) могут уменьшаться как для неокрашенных, так и для окрашенных вершин.
Если для некоторой окрашенной вершины x происходит уменьшение величины d(x), то с этой вершины и инцидентной ей окрашенной дуги окраска снимается.
Процедура алгоритма заканчивается только тогда, когда все вершины окрашены и когда после выполнения шага 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) раза.