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

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

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

Определим алгоритм Форда-Беллмана. Зададим строку D⁽¹⁾ = (d₁⁽¹⁾, d₂⁽¹⁾,…, d_n⁽¹⁾), полагая d_i⁽¹⁾ = 0, d_j⁽¹⁾ = w_ij, i ¹ j. В этой строке d_j⁽¹⁾ (j ¹ i) есть вес w_ij дуги (a_i ¹ a_j), если (a_i,a_j) существует, и d_j⁽¹⁾ = ¥, если (a_i,a_j) Î R. Теперь определим строку D⁽²⁾ = (d₁⁽²⁾, d₂⁽²⁾,…, d_n⁽²⁾), полагая d_j⁽²⁾ = min{ d_j⁽¹⁾, d_k⁽¹⁾ + w_kj } _k=1,…,n. Нетрудно заметить, что d_j⁽²⁾ — минимальный из весов (a_i,a_j)-маршрутов, состоящих не более чем из двух дуг (рис. 4.24).

Продолжая процесс, на шаге s определим строку D^(s) = (d₁^(s), d₂^(s),…, d_n^(s)), полагая d_j^(s) = min{ d_j^(s-1), d_k^(s-1) + w_kj } _k=1,…,n. Искомая строка, w -расстояний получается при s = n - 1: d_j^(n-1) =
p_w (a_i,a_j). Действительно, на этом шаге из весов всех (a_i,a_j)-маршрутов, содержащих по более п - 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⁽¹⁾ = (0,1,¥,¥,3), D⁽²⁾ = (0,1,4,4,3), D⁽³⁾ = (0,1,4,4,-1), D⁽⁴⁾ = (0,1,4,3,-1). Таким образом, p_w (1,1) = 0, p_w (1,2) = 1, p_w (1,3) = 4, p_w (1,4) = 3, p_w (1,5) = -1.

Отметим, что, зная расстояние от источника a_i до всех остальных вершин графа, можно найти и сами кратчайшие (a_i,a_j)-маршруты. Действительно, пусть a_i,b₁,b₂,…,b_r,a_j кратчайший (a_i,a_j)-маршрут. Тогда по строке D^(n-1) вершина b_r = находится из соотношения p_w (a_i,a_j) = p_w (a_i, ) + , вершина b_r-1 = — из соотношения p_w (a_i, ) = p_w (a_i, ) + , и т. д.

Пример 4.5.2. В примере 4.5.1 кратчайший (1,4)-маршрут определяется следующим образом: p_w (1,4) = 3 = -1 + 4 = p_w (1,5) + w ₅₄, тогда b_r = 5; p_w (1,5) = -1 = 4 - 5 = p_w (1,3) + w ₃₅, откуда b_r-1 = 3; p_w (1,3) = 4 = 1 + 3 = w ₁₂ + w ₂₃, следовательно, b_r-1 = b₂ = 3, b_r-3 = b₁ = 2. Таким образом, кратчайший (1,4)-маршрут задается последовательностью вершин (1,2,3, 5,4).

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

Итак, пусть G = (M,R)— взвешенный граф, W = (w_ij)— матрица весов графа G, где w_ij ³ 0; a_i; — выделенный источник. Зададим строку D⁽¹⁾ = (d₁⁽¹⁾, d₂⁽¹⁾,…, d_n⁽¹⁾), полагая, как и в алгоритме Форда-Беллмана, d_i⁽¹⁾ = 0, d_j⁽¹⁾ = w_ij, i ¹ j, Обозначим через T₁ множество вершин M \{ a_i }. Предположим, что на шаге s уже определены строка D^(s) = (d₁^(s), d₂^(s),…, d_n^(s)) и множество вершин T_s. Выберем теперь вершину a_j Î T_s так, что d_j^(s) = min{ d_k^(s) | a_k Î T_s }. Положим Т_s+1 = Т_s \{ а_j }, D^(s+1) = (d₁^(s+1),…, d_n^(s+1)), где d_k^(s+1) = min{ d_k^(s), d_j^(s) + w_jk }, если a_k Î Т_s+1. На шаге s = n -1 образуется строка D^(n-1) w -расстояний между вершиной а_i и остальными вершинами графа: d_j^(n-1) = р_w{а_i,a_j).

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

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

0 1 ¥ ¥ ¥ ¥

¥ 0 5 2 ¥ 7

W =

¥ ¥ 0 ¥ ¥ 1

2 ¥ 1 0 4 ¥

¥ ¥ ¥ 3 0 ¥

¥ ¥ ¥ ¥ 1 0

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

Тогда по алгоритму Дейкстры T₁ = {2,3,4,5,6}, D⁽¹⁾ = (0, 1,¥,¥,¥,¥), T₂ = {3,4,5,6}, D⁽²⁾ = (0,1,6, 3,¥,¥), T₃ = {3,5,6}, D⁽³⁾ = (0,1, 4,3,7,8), T₄ = {5,6}, D⁽⁴⁾ = (0,1,4,3,7, 5); T₅ = {5}, D⁽⁵⁾ = (0,1,4,3,6,5) (в D^(s) подчеркнута величина d_j^(s), для которой T_s.₊₁ = T_s \{ a_j }). Таким образом, р_w (1,1) = 0, р_w (1,2) = 1, р_w (1,3) = 4, р_w (1,4) = 3, р_w (1,5) = 6, р_w (1,6) = 5. □

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

Прежде всего заметим, что в конечном бесконтурном графе G = (М,R)вершины можно перенумеровать так, что каждая дуга будет иметь вид (a_i,a_j), где i < j. Действительно, в конечном бесконтурном графе всегда существует вершина а, в которую не заходит ни одна дуга. Обозначим эту вершину через а₁ и рассмотрим граф G₁,полученный из G удалением вершины а₁. Граф G₁ также является бесконтурным и, следовательно, содержит вершину a¢, в которую не заходит ни одна дуга графа G₁. Вершину a¢ обозначим через а₂, а граф, полученный из G₁ удалением вершины а₂ — через G₂. Продолжая процесс, получим в результате искомую нумерацию a₁, a₂,…, a_n вершин графа G.

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

Предположим, что в бесконтурном графе G = ({ a₁,…, a_n }, R)для произвольной дуги (a_i,a_j)выполняется условие i < j. Заметим, что при такой нумерации все элементы матрицы весов, стоящие под главной диагональю, равны ¥. Найдем расстояние от ai до всех вершин графа. Рассмотрим строку D⁽¹⁾ = (d₁⁽¹⁾, d₂⁽¹⁾,…, d_n⁽¹⁾), где d₁⁽¹⁾ = 0, d_j⁽¹⁾ = w_1j, j ³ 2. Если на шаге s строка D^(s) = (d₁^(s), d₂^(s),…, d_n^(s)) определена, положим D^(s+1) = (d₁^(s+1), d₂^(s+1),…, d_n^(s+1)), где d_j^(s+1) = min{ d_j^(s), d_k^(s) + w_kj }, для k < j и Î R, j = 1,…, n. Данный алгоритм является аналогом алгоритма Форда-Беллмана, учитывающим бесконтурность графа. G, и при s = п – 1 получаем d_j^(n-1) = p_w (a₁,a_j)

Пример 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⁽¹⁾ = (0,1,¥,2,¥,¥,1,¥), D⁽²⁾ = (0,1,-1,2,-3,¥,1,4), D⁽³⁾ = (0,1,-1,2,-3,3,1,
-2) = D⁽⁴⁾ = D⁽⁵⁾ = D⁽⁶⁾ = D⁽⁷⁾. □

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