1.2. Алгоритмы поиска всех кратчайших путей

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

Пример 1. Предположим, что авиакомпания, фигурировавшая в при­мере 2 разд. 3.1, должна для многочисленных пассажиров ежедневно раз­рабатывать маршруты полетов между различными городами. Эта авиаком­пания в целях экономии своих затрат стремится предоставлять пассажирам наиболее короткие маршруты. Поэтому ей хотелось бы заранее знать крат­чайшие маршруты между каждой парой городов США, если, например, речь идет о полетах в пределах США.

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

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

В алгоритме Флойда в качестве исходной выступает матрица . Вначале из этой матрицы вычисляется матрица . Затем по матрице вычисляется матрица и т. д. Процесс повторяется до тех пор, пока по матрицене будет вычислена матрица.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Предположим, что нам известны:

а) кратчайший путь из вершины i в вершину т_, в котором в качестве промежуточных допускается использование только первых (т — 1) вершин;

б) кратчайший путь из вершины т в вершину j, в котором в качестве промежуточных допускается использование только первых (т — 1) вершин;

в) кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m — 1) вершин.

Поскольку по предположению исходный граф не может содер­жать контуров отрицательной длины, один из двух путей — путь, совпадающий с представленным в п. «в», или путь, являющийся объединением путей из пп. «а» и «б», —должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточ­ных допускается использование только первых т вершин. Таким образом,

(3)

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

Алгоритм Флойда

Шаг 1. Перенумеровать вершины исходного графа целыми чис­лами от 1 до N. Определить матрицу , задав величину каждого ее элемента (i,j) равной длине кратчайшей дуги, соединяющей вершину i с вершиной j. Если в исходном графе указанные вершины не соединяются дугами, положить . Кроме того, для всех

i положить .

Шаг 2. Для целого т, последовательно принимающего значе­ния , определить по величинам элементов матрицы величины элементов матрицы , используя рекурсивное соотно­шение (3), т. е. соотношение

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

По окончании данной процедуры величина элемента (i, j) матри­цы определяет длину кратчайшего пути, ведущего из вершины i в вершину j.

То, что описанный алгоритм действительно находит кратчай­шие пути, может быть индуктивно доказано на основе следующего факта. Длина кратчайшего пути из вершины i в вершину j, допус­кающего использование в качестве промежуточных первых m вер­шин, должна быть не больше длины кратчайшего пути из i в j, допускающего использование в качестве промежуточных первых (m — 1) вершин, и не больше длины кратчайшего пути из i в j, допускающего использование в качестве промежуточных первых (т — 1) вершин и обязательно — вершины т.

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

Пример 2. (Применение алгоритма Флойда). Для графа, изображен­ного на рис. 3.1, матрица , составленная из длин дуг графа,такова:

Величины элементов матрицы и соответствующие им кратчайшие пути определяются следующим образом:

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

Матрица :

Кратчайшие пути для элементов матрицы :

Матрица :

Кратчайшие пути для элементов матрицы :

Матрица :

Кратчайшие пути для элементов матрицы :

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

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

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

Существуют два способа определения — встроенный (tenta­tive) и внешний (terminal). Опишем каждый из них в отдельности.

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

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

2. Внешний способ. Считая работу алгоритма Флойда закон­ченной, а значит, и зная матрицу ,определить каждое , положив его равным любому k, для которого ; при этом для формирования требуются только матрицы D⁰ и D^N.

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

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

Итак, рассмотрим алгоритм Данцига. Снова перенумеруем вер­шины исходного графа целыми числами от 1 до N и обозначим через длину кратчайшего пути из вершины i в вершину j, в котором допускается использование в качестве промежуточных т первых вершин графа. Пусть теперь в отличие от алгоритма Флойда мат­рица , состоящая из величин , при каждом имеет размерность не (NхN), а (т х т). Так же, как и раньше, требуется определить матрицу ,элемент (i, j) которой определя­ет длину кратчайшего пути из вершины i в вершину j. Как и в алгоритме Флойда, в алгоритме Данцига матрица определя­ется из матрицы , матрица из матрицы и т. д. Наконец, матрица определяется из матрицы .

В чем же идея алгоритма Данцига? Во-первых, отметим, что каждая новая вычисляемая матрица содержит на одну строку и на один столбец больше, чем ее предшественница, матрица . Элементы матрицы, не входящие в последние строку и столбец (число таких элементов равно , определяются точно так же, как в алгоритме Флойда. Что же касается остальных элемен­тов, где или., то они определяются с учетом при­водимых ниже соображений. Кратчайший путь из вершины i в вершину т (или наоборот), в котором допускается использова­ние в качестве промежуточных только первых т вершин графа, не может иметь среди промежуточных вершину т, поскольку лю­бой контур в исходном графе имеет неотрицательную длину. В си­лу данного обстоятельства такой кратчайший путь из вершины i в вершину т должен иметь своей первой частью кратчайший путь из вершины i в некоторую вершину , который допускает использование в качестве промежуточных только первых вершин графа, а второй частью — кратчайшую дугу, ведущую из вершиныj в вершину т (конечно, следует рассматривать только такие вершины j, для которых имеется хотя бы одна дуга, ведущая из j в т). Аналогично кратчайший путь из вершины т в вершину i, в котором допускается использование в качестве промежуточных только т первых вершин графа, должен иметь своей первой частью кратчайшую дугу, ведущую из вершины т в некоторую вершину , а второй частью — кратчайший путь из вершины j в. вершину i, который допускает использование в качестве проме­жуточных только (т — 1) первых вершин (конечно, следует рас­сматривать только такие вершины j, для которых имеется хотя бы одна дуга, ведущая из m в j). Наконец, отметим, что величины должны полагаться равными нулю.

С учетом приведенных соображений мы можем теперь формаль­но описать алгоритм Данцига.

Алгоритм Данцига поиска всех кратчайших путей

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

Шаг 2. Здесь через обозначается матрица размерностью с элементами.Последовательно опре­делить элементы матрицы из элементов матрицы для т, принимающего значения :

(4)

₍₅₎

(6)

Кроме того, для всех i и т положить

(7)

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

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

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

Перейдем теперь к определению числа операций в алгоритмах Флойда (Данцига), Дейкстры и Форда. В алгоритме Флойда вы­числяются N матриц,каждая из которых состоит из элементов. Следовательно, в алгоритме Флойда необходимо вычислять элементов. Каждое такое вычисление осуществляет­ся с помощью соотношения (3) и требует выполнения одной опе­рации сложения и одной операции сравнения. Следовательно, в алгоритме Флойда выполняется сложений исравнений. (Строго говоря, указанные числа несколько превышают действительные показатели, поскольку некоторые элементы матрицымогут быть непосредственно приравнены соответствующим элемен­там из матрицыбез проведения вычислений с помощью соот­ношения (3). Это относится к элементамi-й строки и i-го столбца матриц и , являющихся в этих матрицах одинаковыми.) Итак, общее количество операций, выполняемых в алгоритме Флойда, пропорционально Используя более строгую термино­логию, этот результат можно сформулировать следующим образом: алгоритм Флойда требует для своего выполнения времени счета порядка0 ().

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

3(N-2) операций, третья 3(N-3) операций и т. д. Общее число операций в алгоритме Дейкстры определяется соотношением

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

Таким образом, нами получены следующие результаты: в алго­ритме Дейкстры выполняется операций; в алгоритме Фор­да в наихудшем случае выполняется операций; в алгоритме Флойда выполняетсяопераций; в алгоритме Данцига выпол­няется операций.

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