Задача о кратчайших путях между всеми парами узлов.

В предыдущих параграфах этой главы рассматривались задачи нахождения оптимальных в том или ином смысле путей от неко­торого фиксированного узла до всех остальных узлов сети. Здесь мы рассмотрим задачу построения кратчайших путей между все­ми парами узлов. Под длиной пути, также как и ранее в парагра­фах 1-3, понимаем сумму весов дуг, образующих этот путь. Ясно, что эту задачу можно решать, используя n раз (поочередно для каждого узла) один из описанных ранее алгоритмов нахождения расстояний от фиксированного узла. Таким образом, мы получа­ем алгоритмы сложности O(n⁴) (при использовании алгоритма Форда-Беллмана) и O(n³) для сетей с неотрицательными весами (алгоритм Дейкстры) или для бесконтурных сетей (алгоритм 6.6). Однако, для общего случая сетей с произвольными весами име­ются более эффективные алгоритмы, чем метод, основанный на п-кратном применении алгоритма Форда-Беллмана. Один из та­ких алгоритмов, предложенный в 1962 году Флойдом, мы здесь и разберем.

Пусть сеть G=(V,E,c) задана матрицей весов А, где А| i,j | c(v_i,v_j), и A[i,j]=+∞, если дуги (v_i,v_j) в сети нет.

Обозначим через d_k(i,j) длину кратчайшего пути из v_i и v_j, все промежуточные узлы которого содержатся в множестве {v₁,...,v_k}, то есть содержатся в первых к узлах. Будем считать, что d₁(i,j)=A[i,j]. Пусть d_k(i,j) вычислено для всех i,j=l,...,n, и не­котором k≥1. Докажем равенство

d_k+1(i,j) = min(d_k(i,j), d_k(i,k+l) + d_k(k+l, j)). (6.5)

Действительно, рассмотрим кратчайший v_i-v_j-путь р с проме­жуточными узлами из множества {v₁,…,v_k,v_k+1}. Возможны две ситуации: либо узел v_k+1 входит в этот путь, либо нет.

Если узел v_k+1 не входит в путь р, то, как легко видеть, спра­ведливо равенство d_k+1(i,j)= d_k(i,j).

Если же узел v_k+1 входит в путь р, то разбивая это путь на пути от v, до v_k+1 и от v_k+1 до v_j, получаем два новых пути, все проме­жуточные узлы которых входят во множество {v₁,...,v_k}. По­скольку всякий подпуть кратчайшего пути сам является крат­чайшим путем между соответствующими узлами, то справедливо равенство d_k+1(i,j) = d_k(i,k+l) + d_k(k+l,j)), что завершает обосно­вание равенства (6.5).

Равенство (6.5) позволяет легко вычислять расстояния между всеми парами узлов, последовательно вычисляя для всех пар уз­лов значения d₁(i,j). d₂(i,j),..., d_n(i,j), так как расстояние от v₁ до v_j равно d_n(i,j).

Для нахождения самих кратчайших путей будем использовать аналог неоднократно применявшегося ранее массива ОТЕЦ, а именно, заведем матрицу ПРЕД размера n n, в которой ПРЕД[i,j] дает номер узла, являющегося предпоследним в кратчайшем v_i-v_j- пути (понятно, что последним узлом в таком пути является узел v_j). Если k=ПРЕД[i,j], то, посмотрев значение ПРЕД[i,k], получим следующий узел в v_i-v_j-пути. Таким образом, двигаясь по эле­ментам матрицы ПРЕД, легко построить путь для любой пары узлов.

Детали изложены в алгоритме 6.9, где предполагается, что A[i,i]=0, A[i,j]=+∞, если (v_i,v_j) Е. Еще раз повторим, что неотри­цательность весов дуг не предполагается, но считается, что в сети нет контуров отрицательной длины.

АЛГОРИТМ 6.10 ФЛОЙД

(* Вычисление расстояний между всеми парами узлов *)

Данные: Сеть G=(V,E,c), заданная матрицей весов А[...n, 1...n].

Результаты: Расстояния D[i,j] для всех пар v_i, v_j V. матрица ПРЕД, в которой ПРЕД[v] равно номеру предпоследнего узла в кратчайшем v_i-v_j -пути.

Понятно, что сложность алгоритма 6.10 определяется сложно­стью цикла в строках 5-9, который состоит из трех вложенных циклов, выполняемых n раз каждый. Отсюда следует

Теорема 6.7. Алгоритм Флойда имеет сложность O(n³).

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

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

Завершим главу рассмотрением примера, иллюстрирующего работу алгоритма Флойда.

Результаты работы цикла в строках 2-6:

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=1

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=2

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=3

D= ПЕРЕД=

Нетрудно проверить, что обе эти матрицы останутся неизмен­ными в результате работы цикла 7-13 при k = 4. Вот кратчайшие пути для некоторых пар узлов: 2-4: 2-3-1-4; 1-3: 1-2-3; 3-2: 3-1-2.

ЗАДАЧИ

1.Пути в орграфе с взвешенными узлами. Пусть G=(V,E) — орграф с заданной функцией весов узлов: d: V -» R. Для s-t-пути р: v₀=s,vi,...,vk=t в орграфе G, положим

d(p)=∑{d(v_r): r=l,2,...k}.

Свести задачу о построении s-t-пути р в G с минимальным значением d(p) к задаче о построении кратчайшего пути между s и t в подходяще построенной сети.

2.Пути в сетях с взвешенными узлами. Пусть G=(V,E,c) — сеть с заданной функцией весов узлов d: V→R. Для s-t-пути р: v₀=s,v₁,...,v_k=t в сети G положим

f(p)= ∑{c(v_r-1,v_r) + d(v_r)}.

Свести задачу о построении s-t-пути в G с минимальным зна­чением f(p) к задаче о построении кратчайшего пути в подходяще построенной сети.

3.Пути между фиксированными множествами узлов. Пусть в сети G=(V,E,c) зафиксировано два множества узлов S и T, S T=Ø. Требуется среди всех путей, начинающихся в каком-нибудь узле множества S и заканчивающихся в каком-нибудь уз­ле из множества Т. найти путь минимальной стоимости. Свести эту задачу к задаче о кратчайшем пути между фиксированными узлами.

4.Напишите алгоритм сложности О(m), осуществляющий топологическую сортировку узлов бесконтурного орграфа, за­данного списками СЛЕД. Указание: докажите, что каждый такой орграф содержит хотя бы один узел, степень захода которого равна нулю. Начните нумерацию по возрастанию номеров со всех таких узлов, удаляя каждый раз пронумерованный узел вместе со теми дугами, из него выходящими. Предложите алгоритм слож­ности О(n²), осуществляющий топологическую сортировку узлов беcконтурного орграфа, заданного матрицей смежности.

5.Напишите алгоритм сложности О(m), вычисляющий расстояния от v до всех остальных узлов в бесконтурной топологически отсортированной сети, заданной списками смежностей СЛЕД, и алгоритм сложности O(n²) для сети, заданной матрицей несом.

6.Промышленная компания планирует начать производство кондиционеров, состоящих из трех основных частей: корпуса, вентилятора и мотора. Затраты на оборудование предприятия станками, производящими корпуса, вентиляторы и моторы, со­ставляют 20000, 50000 и 80000 руб. соответственно. Если вначале наладить выпуск вентиляторов, то затраты на оборудование предприятия станками, производящими корпуса и моторы, будут уменьшены на 5%. Если вначале пустить в производство моторы, то затраты на оснащение предприятия станками двух других ти­пов уменьшатся на 10%. Если же в первую очередь будет нала­жен выпуск корпусов, то остальные затраты уменьшатся на 5%. После того, как будет налажен выпуск двух компонентов, затра­ты на производство третьего компонента дополнительно умень­шатся на 5% Как организовать производство с наименьшими за­тратами?

7.Промышленной компании нужно составить план замены оборудования на ближайшие 4 года. На данный период ожидают­ся следующие расходы и амортизационные стоимости. Сущест­вующая цена станка составляет 20000 ед. Ожидается ежегодное увеличение цен па станки на 10%. В первые два года станки из­нашиваются на 25%, а в последующие два года — на 15%. Из­держки на техническое обслуживание и текущий ремонт в бли­жайшие 4 года составят 1200, 1500, 1900 и 2400 ед. соответствен­но. Станки можно заменять каждый год или каждые 2, 3 и 4 года. Составить план замены оборудования, при котором общие из­держки на ближайшие 4 года были бы минимальными.

8.Крупную партию груза требуется доставить из пункта А в пункт В. Вывезти груз из А можно двумя способами: либо грузо­выми самолетами до пункта С, либо морским путем до порта D. Из пункта С до В груз можно доставить автотранспортом, стои­мость перегрузки 1 тонны с самолетов в автомобили составляет 0,4 ед. Из порта D продукция может быть либо доставлена в пункт В по железной дороге, в этом случае стоимость перегрузки 1 тонны с морских барж в железнодорожные вагоны составляет 0,2 ед., либо транзитом через пункт С доставлена автотранспор­том. при этом стоимость перегрузки с морских барж в автомобили составляет 0,3 ед. за 1 тонну. Стоимость перевозки 1 тонны груза дана в таблице:

Найти наиболее экономичный способ доставки груза из пунк­та А в пункт В.

9.На схеме дана информационная сеть. Числа в скобках да­ют вероятность искажения информации при использовании дан­ного канала.

Найти самый надежный путь пересылки сообщения из s в t, считая, что искажения информации при использовании разных каналов не зависят друг от друга.

10.Напишите процедуру, строящую кратчайший v_i-v_j -путь, использующую в качестве исходных данных матрицу ПРЕД (см. алгоритм 6.9).

11.Найдите кратчайшие пути между всеми парами узлов в сети, заданной матрицей:

A=

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

13.Предложите алгоритм вычисления minmax расстояний между всеми парами узлов заданной сети, имеющий сложность O(n³). Аналогичный вопрос для вычисления maxmin расстояний. Опишите процедуру построения соответствующих кратчайших путей между всеми парами узлов. Предполагается, что сеть зада­на матрицей ПРЕДШ.

14.Исследуйте задачу построения минимального по числу дуг пути в maxmin-задаче о кратчайшем пути.

15.Предложите алгоритм, который по данной (n n)-матрице М положительных целых чисел строит последовательность смежных элементов, начинающуюся с М[n,1] и оканчивающуюся М[1,n] так, чтобы минимизировать сумму модулей разностей ме­жду соседними элементами. При этом элементы матрицы счита­ются соседними, если они смежны по вертикали или по горизон­тали.

16.Предложите алгоритм, который распознавал бы, имеется или нет в данной сети с произвольными весами дуг контур отри­цательной стоимости.

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