Нахождение кратчайших маршрутов



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Нахождение кратчайших маршрутов



Пусть G = (М, R)взвешенный граф, имеющий п вершин и матрицу весов W = (wij), Î R. Опишем некоторые методы нахождения взвешенного расстояния от фиксированной вершины ai Î М (называемой источником) до всех вершин графа G.

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

Определим алгоритм Форда-Беллмана. Зададим строку D(1) = (d1(1), d2(1),…, dn(1)), полагая di(1) = 0, dj(1) = wij, i ¹ j. В этой строке dj(1) (j ¹ i) есть вес wij дуги (ai ¹ aj), если (ai,aj) существует, и dj(1) = ¥, если (ai,aj) Î R. Теперь определим строку D(2) = (d1(2), d2(2),…, dn(2)), полагая dj(2) = min{dj(1), dk(1) + wkj}k=1,…,n. Нетрудно заметить, что dj(2) — минимальный из весов (ai,aj)-маршрутов, состоящих не более чем из двух дуг (рис. 4.24).

Продолжая процесс, на шаге s определим строку D(s) = (d1(s), d2(s),…, dn(s)), полагая dj(s) = min{dj(s-1), dk(s-1) + wkj}k=1,…,n. Искомая строка, w-расстояний получается при s = n - 1: dj(n-1) =
pw(ai,aj). Действительно, на этом шаге из весов всех (ai,aj)-маршрутов, содержащих по более п - 1 дуг, выбирается наименьший, а каждый маршрут более чем с п - 1 дугами содержит контур, добавление которого к маршруту не уменьшает w-расстояния, так как мы предположили отсутствие контуров отрицательного веса. Работу алгоритма можно завершить на шаге k, если D(k) = D(k+1)

Пример 4.5.1. Продемонстрируем работу алгоритма Форда-Беллмана на примере взвешенного графа, показанного на, рис 4.25, с матрицей весов

0 1 ¥ ¥ 3

¥ 0 3 3 8

.
W =
¥ ¥ 0 1 -5

¥ ¥ 2 0 ¥

¥ ¥ ¥ 4 0

В качестве источника выберем вершину 1. Тогда D(1) = (0,1,¥,¥,3), D(2) = (0,1,4,4,3), D(3) = (0,1,4,4,-1), D(4) = (0,1,4,3,-1). Таким образом, pw(1,1) = 0, pw(1,2) = 1, pw(1,3) = 4, pw(1,4) = 3, pw(1,5) = -1.

Отметим, что, зная расстояние от источника ai до всех остальных вершин графа, можно найти и сами кратчайшие (ai,aj)-маршруты. Действительно, пусть ai,b1,b2,…,br,aj кратчайший (ai,aj)-маршрут. Тогда по строке D(n-1) вершина br = находится из соотношения pw(ai,aj) = pw(ai, ) + , вершина br-1 = из соотношения pw(ai, ) = pw(ai, ) + , и т. д.

Пример 4.5.2. В примере 4.5.1 кратчайший (1,4)-маршрут определяется следующим образом: pw(1,4) = 3 = -1 + 4 = pw(1,5) + w54, тогда br = 5; pw(1,5) = -1 = 4 - 5 = pw(1,3) + w35, откуда br-1 = 3; pw(1,3) = 4 = 1 + 3 = w12 + w23, следовательно, br-1 = b2 = 3, br-3 = b1 = 2. Таким образом, кратчайший (1,4)-маршрут задается последовательностью вершин (1,2,3, 5,4).

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

Итак, пусть G = (M,R)— взвешенный граф, W = (wij)— матрица весов графа G, где wij ³ 0; ai; — выделенный источник. Зададим строку D(1) = (d1(1), d2(1),…, dn(1)), полагая, как и в алгоритме Форда-Беллмана, di(1) = 0, dj(1) = wij, i ¹ j, Обозначим через T1 множество вершин M\{ai}. Предположим, что на шаге s уже определены строка D(s) = (d1(s), d2(s),…, dn(s)) и множество вершин Ts. Выберем теперь вершину aj Î Ts так, что dj(s) = min{dk(s)|ak Î Ts}. Положим Тs+1 = Тs\{аj}, D(s+1) = (d1(s+1),…, dn(s+1)), где dk(s+1) = min{dk(s), dj(s) + wjk}, если ak Î Тs+1. На шаге s = n-1 образуется строка D(n-1) w-расстояний между вершиной аi и остальными вершинами графа: dj(n-1) = рwi,aj).

Отметим, что для реализации алгоритма Форда-Беллмана требуется порядка n3 операций, тогда как в алгоритме Дейкстры необходимо выполнить порядка n2 операций.

Пример 4.5.3. Рассмотрим взвешенный граф G с матрицей весов

0 1 ¥ ¥ ¥ ¥

¥ 0 5 2 ¥ 7

W =
¥ ¥ 0 ¥ ¥ 1

2 ¥ 1 0 4 ¥

¥ ¥ ¥ 3 0 ¥

¥ ¥ ¥ ¥ 1 0

и источником 1 (рис. 4.26).

Тогда по алгоритму Дейкстры T1 = {2,3,4,5,6}, D(1) = (0,1,¥,¥,¥,¥), T2 = {3,4,5,6}, D(2) = (0,1,6,3,¥,¥), T3 = {3,5,6}, D(3) = (0,1,4,3,7,8), T4 = {5,6}, D(4) = (0,1,4,3,7,5); T5 = {5}, D(5) = (0,1,4,3,6,5) (в D(s) подчеркнута величина dj(s), для которой Ts.+1 = Ts\{aj}). Таким образом, рw(1,1) = 0, рw(1,2) = 1, рw(1,3) = 4, рw(1,4) = 3, рw(1,5) = 6, рw(1,6) = 5. □

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

Прежде всего заметим, что в конечном бесконтурном графе G = (М,R)вершины можно перенумеровать так, что каждая дуга будет иметь вид (ai,aj), где i < j. Действительно, в конечном бесконтурном графе всегда существует вершина а, в которую не заходит ни одна дуга. Обозначим эту вершину через а1 и рассмотрим граф G1,полученный из G удалением вершины а1. Граф G1 также является бесконтурным и, следовательно, содержит вершину , в которую не заходит ни одна дуга графа G1. Вершину обозначим через а2, а граф, полученный из G1 удалением вершины а2через G2. Продолжая процесс, получим в результате искомую нумерацию a1, a2,…, an вершин графа G.

Пример 4.5.4. На рис. 4.27 приведен пример нумерации вершин бесконтурного взвешенного графа, при которой из (ai,aj) Î R. следует i < j (в скобках указаны веса взвешенных дуг). □

Предположим, что в бесконтурном графе G = ({a1,…, an},R)для произвольной дуги (ai,aj)выполняется условие i < j. Заметим, что при такой нумерации все элементы матрицы весов, стоящие под главной диагональю, равны ¥. Найдем расстояние от ai до всех вершин графа. Рассмотрим строку D(1) = (d1(1), d2(1),…, dn(1)), где d1(1) = 0, dj(1) = w1j, j ³ 2. Если на шаге s строка D(s) = (d1(s), d2(s),…, dn(s)) определена, положим D(s+1) = (d1(s+1), d2(s+1),…, dn(s+1)), где dj(s+1) = min{dj(s), dk(s) + wkj}, для k < j и Î R, j = 1,…, n. Данный алгоритм является аналогом алгоритма Форда-Беллмана, учитывающим бесконтурность графа. G, и при s = п – 1 получаем dj(n-1) = pw(a1,aj)

Пример 4.5.5. Для графа G (рис. 4.27) имеем

0 1 ¥ 2 ¥ ¥ 1 ¥

¥ 0 -2 ¥ 7 ¥ ¥ ¥

¥ ¥ 0 ¥ ¥ 10 ¥ ¥

,
S = C + Q =
¥ ¥ ¥ 0 -5 ¥ ¥ ¥

¥ ¥ ¥ ¥ 0 6 ¥ 1

¥ ¥ ¥ ¥ ¥ 0 ¥ ¥

¥ ¥ ¥ ¥ ¥ ¥ 0 3

¥ ¥ ¥ ¥ ¥ ¥ ¥ 0

D(1) = (0,1,¥,2,¥,¥,1,¥), D(2) = (0,1,-1,2,-3,¥,1,4), D(3) = (0,1,-1,2,-3,3,1,
-2) = D(4) = D(5) = D(6) = D(7). □

Отметим, что если в приведенных алгоритмах ¥ заменить на -¥, min — на max, то получим алгоритмы, которые позволяют в графах, не имеющих контуров положительных весов, находить маршруты наибольшей длины.

 



Последнее изменение этой страницы: 2016-04-07; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.118.225 (0.008 с.)