Кратчайшие пути

В этом разделе рассматриваются различные варианты одной задач. Пусть имеется n городов, пронумерованных числами от 1 до n. Для каждой пары городов с номерами i, j в таблице a[i][j] хранится целое число -- цена прямого авиабилета из города i в город j. Считается, что рейсы существуют между любыми городами, ${\hbox{\tt a[i][i]}}={\hbox{\tt 0}}$ при всех i, a[i][j] может отличаться от a[j][i]. Наименьшей стоимостью проезда из i в j считается минимально возможная сумма цен билетов для маршрутов (в том числе с пересадками), ведущих из i в j. (Она не превосходит a[i][j], но может быть меньше.)  

В предлагаемых ниже задачах требуется найти наименьшую стоимость проезда для некоторых пар городов при тех или иных ограничениях на массив a и на время работы алгоритма.


$\scriptstyle{\blacktriangleright}$ 9.1.1. Предположим, что не существует замкнутых маршрутов, для которых сумма цен отрицательна. Доказать, что в этом случае маршрут с наименьшей стоимостью существует.

Решение. Маршрут длиной больше n всегда содержит цикл, поэтому минимум можно искать среди маршрутов длиной не более n, а их конечное число.$\scriptstyle\blacktriangleleft$

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


$\scriptstyle{\blacktriangleright}$ 9.1.2. Найти наименьшую стоимость проезда из 1-го города во все остальные за время $O({\hbox{\tt n}}^3)$.

  

Решение. 2pt Обозначим через МинСт(1,s,к) наименьшую стоимость проезда из 1 в s менее чем с k пересадками. Тогда выполняется такое соотношение: \begin{displaymath} \displaylines{\quad {\hbox{\tt МинСт}}({\hbox{\tt 1}},{\hbo... ...нСт(1,i,k)}}+{\hbox{\tt a[i]}}\!{\hbox{\tt [s]}})\Bigr). \quad}\end{displaymath}Как отмечалось выше, искомым ответом является МинСт(1,i,n) для всех ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt n}}$.
     k:= 1;
     for i := 1 to n do begin x[i] := a[1][i]; end;
     {инвариант: x[i] := МинСт(1,i,k)}
     while k <> n do begin
     | for s := 1 to n do begin
     | | y[s] := x[s];
     | | for i := 1 to n do begin
     | | | if y[s] > x[i]+a[i][s] then begin
     | | | | y[s] := x[i]+a[i][s];
     | | | end;
     | | end
     | | {y[s] = МинСт(1,s,k+1)}
     | end;
     | for i := 1 to n do begin x[s] := y[s]; end;
     | k := k + 1;
     end;
Приведенный алгоритм называют алгоритмом динамического программирования, или алгоритмом Форда-Беллмана.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.3. Доказать, что программа останется правильной, если не заводить массива y, а производить изменения в самом массиве x (заменив в программе все вхождения буквы y на x и затем удалить ставшие лишними строки).

Решение. Инвариант будет таков: \begin{displaymath} {\hbox{\tt МинСт(1,i,n)}} \leqslant{\hbox{\tt x[i]}} \leqslant{\hbox{\tt MинСт(1,i,k)}}.\end{displaymath}

Этот алгоритм может быть улучшен в двух отношениях: можно за то же время $O({\hbox{\tt n}}^3)$ найти наименьшую стоимость проезда ${\hbox{\tt i}}\rightarrow{\hbox{\tt j}}$ для всех пар i,j (а не только при ${\hbox{\tt i}}={\hbox{\tt 1}}$), а можно сократить время работы до $O({\hbox{\tt n}}^2)$. Правда, в последнем случае нам потребуется, чтобы все цены a[i][j] были неотрицательны.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.4. Найти наименьшую стоимость проезда ${\hbox{\tt i}}\rightarrow{\hbox{\tt j}}$для всех i,j за время $O({\hbox{\tt n}}^3)$.

 

Решение. Для ${\hbox{\tt k}} = {\hbox{\tt 0}}\ldots{\hbox{\tt n}}$ через A(i,j,k) обозначим наименьшую стоимость маршрута из i в j, если в качестве пересадочных разрешено использовать только пункты с номерами не больше k. Тогда (два варианта соответствуют неиспользованию и использованию пункта k+1 в качестве пересадочного; отметим, что в нем незачем бывать более одного раза).

Этот алгоритм называют алгоритмом Флойда.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.5. Известно, что все цены неотрицательны. Найти наименьшую стоимость проезда ${\hbox{\tt 1}}\rightarrow{\hbox{\tt i}}$ для всех ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt n}}$ за время $O({\hbox{\tt n}}^2)$.

 

Решение. В процессе работы алгоритма некоторые города будут выделенными (в начале -- только город 1, в конце -- все). При этом:

Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути -- уже до него путь длиннее! (Здесь существенна неотрицательность цен.)

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

При самом бесхитростном способе хранения множества выделенных городов (в булевском векторе) добавление одного города к числу выделенных требует времени $O({\hbox{\tt n}})$.

Этот алгоритм называют алгоритмом Дейкстры.$\scriptstyle\blacktriangleleft$

Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц.   Пусть A -- матрица цен одной авиакомпании, а B -- матрица цен другой. Пусть мы хотим лететь с одной пересадкой, причем сначала самолетом компании A , а затем -- компании B . Сколько нам придется заплатить, чтобы попасть из города i в город j?


$\scriptstyle{\blacktriangleright}$ 9.1.6. Доказать, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения -- сумму.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.7. Доказать, что таким образом определенное произведение матриц ассоциативно.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.8. Доказать, что задача о кратчайших путях эквивалентна вычислению $A^\infty$ для матрицы цен A : в последовательности $A, A^2, A^3,\ldots$ все элементы, начиная с некоторого, равны искомой матрице стоимостей кратчайших путей. (Если нет отрицательных циклов!)$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 9.1.9. Начиная с какого элемента можно гарантировать равенство в предыдущей задаче?$\scriptstyle\blacktriangleleft$

Обычное (не модифицированное) умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть не все рейсы (как раньше), а только некоторые, a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый элемент.


$\scriptstyle{\blacktriangleright}$ 9.1.10. Чему он равен?

Ответ. Числу различных способов попасть из i в j за k рейсов (с k-1 пересадками).$\scriptstyle\blacktriangleleft$ 

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


$\scriptstyle{\blacktriangleright}$ 9.1.11. Доказать, что алгоритм Дейкстры можно модифицировать так, чтобы для n городов и m рейсов (всего) он требовал не более $C(n+m)\log n$ операций.

 

[Указание. Что надо сделать на каждом шаге? Выбрать невыделенный город с минимальной стоимостью и скорректировать цены для всех городов, в которые из него есть маршруты. Если бы кто-то сообщал нам, для какого города стоимость минимальна, то хватило бы C(n+m) действий. А поддержание сведений о том, какой элемент в массиве минимален (см. задачу здесь) обходится еще в множитель $\log n$.]$\blacktriangleleft$


pvv
1/8/1999