Лекция 3. Кратчайшие пути между всеми парами узлов

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

Пусть , , , …,, - кратчайший путь из V_i в V_q. Тогда кратчайший путь из V_i в V_j должен представлять собой единственную дугу е_ij , кратчайший путь из V_j в V_k — дугу e_jk, и т. д.

Назовем дугу е_ij базисной, если она представляет собой кратчайший путь из V_i в V_j. Из данного определения следует, что кратчайший путь состоит только из базисных дуг.

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

(3.1)

Операция выполняется для каждого фиксированного j и всевозможных i и k, не равных j. Для трех узлов V_j, V_j и V_k и трех дуг с длинами d_ik , d_ij и d_jk данная операция сравнивает длину дуги е_ik , с длиной пути, состоящего из двух дуг, с промежуточным узлом V_j. Этот случай показан на рис. 8. Операция (2.1) называется тройственной операцией.

Рис. 8.

Для всевозможных пар узлов V_i и V_k, смежных с V_j , выполним следующие операции.

- Если d_ik d_ij + d_jk, то никаких действий не производим.

- Если d_ik > d_ij + d_jk,, то создаем новую дугу, ведущую из V_i в V_k с d_ik = d_ij + d_jk .

Схема алгоритма:

1) Фиксируем j = 1 и выполняем тройственную операцию (3.1) для всех i, k = 2,3, . . . , n.

2) Фиксируем j = 2 и выполняем тройственную операцию (3.1) для всех i, k = 1, 3, . . . , n.

Замечание. Все новые дуги, добавленные при j = 1, используются далее при j = 2, и т.д.

Как только все тройственные операции будут выполнены для j = n, сеть будет состоять только из базисных дуг и, числа, приписанные каждой ориентированной дуге, ведущей из V_p в V_q, являются кратчайшими расстояниями из V_p в V_q. Докажем это утверждение на примере.

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

Рассмотрим кратчайший путь, изображенный на рис. 9.

Рис. 9.

При j = 1 тройственная операция создает новую дугу с d₆₃ = d₆₁ + d₁₃.

При j = 2 тройственная операция никак не скажется на данном отдельном кратчайшем пути.

При j = 3 дуга с d₆₃ ⁼ d₆₁ + d₁₃ уже построена, следовательно, тройствен­ная операция построит дугу с d₆₃ = d₆₃ + d₃₉ = (d₆₁ + d₁₃) + d₃₉.

При j = 4 будет построена дуга с d₂₆ = d₂₄ + d₄₆.

При j = 6 будет построена дуга длины d₂₉= d₂₆ + d₆₉=(d₂₄ + d₄₆) + (d₆₃ + d₃₉)= d₂₄ + d₄₆ + d₆₁ + d₁₃ + d₃₉.

На рис. 9 построенные дуги изображены пунктирной линией. Числа рядом указывают порядок, в котором эти дуги появлялись. Таким образом, базисная дуга е₆₃ построена первой, а базисная дуга е₆₉ построена второй. Некоторые базисные дуги, которые также будут построены в результате тройственной операции, например, e₄₁ , не изображены на рисунке, так как они не влияют на рассматриваемый кратчайший путь.

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

Замечание 2. Если в сети отсутствуют отрицательные циклы, то любой кратчайший путь должен быть простым и должен состоять не более чем из n - 1 дуг и не более чем из n - 2 различных промежуточных узлов.

Приведенный алгоритм легко может быть запрограммирован на компьютере. Длины дуг сети с n узлами могут быть заданы массивом n х n.

Пример 3.1. Для сети, изображенной на рис. 10, матрица расстояний представлена в таблице 1.

Рис. 10. Сеть, пример 2

При j = 1 мы сравниваем каждый элемент d_i,k () с d_j,1 + d_1,k.

Если d_i,k >d_j,1 + d_1,k, то элемент d_i,k заменяется на эту сумму. В противном случае элемент не меняется.

Табл. 1. Матрица расстояний, пример 2

При j = 2 мы сравниваем каждый элемент d_i,k () с d_j,2 + d_2,k. Минимум из чисел d_i,k и d_j,2 + d_2,k становится новым значением элемента d_i,k.

Замечание 3. В описанных вычислениях при j = 2 мы использовали результаты, полу­ченные при j = 1.

Для фиксированного значения j мы должны просмотреть элементы в (n — 1) х (n — 1) матрице (диагональные элементы всегда равны 0). Каждый элемент сравнивается с суммой двух других элементов: один из той же строки и один из того же столбца. Алгоритм завершает свою работу, когда мы заканчиваем вычисления для j = n.

Замечание 4. Все длины в неориентированной сети симметричны, поэтому достаточно вычислить только одну из двух длин.

Решение примера 2.1. Выполним тройственную операцию для j = 1,2,3,4,5 и запишем только вычисления, которые приводят к изменению в матрице расстояний.

При j = 1

d₂₅ = min{d₂₅, d₂₁ + d₁₅} = min{∞, 1 + 4} = 5.

Изменения расстояний занесены в табл. 2

Табл. 2.

При j = 2

d₁₃ = min{d₁₃, d₁₂ + d₂₃} = min{∞, 1 + 5} = 6,

d₁₄ = min{d₁₄, d₁₂ + d₂₄} = min{∞, 1 + 1} = 2,

d₃₅ = min{d₃₅, d₃₂ + d₂₅} = min{∞, 5 + 5} = 10.

Изменения расстояний занесены в табл. 3.

При j = 3

изменений нет.

При j = 4

d₁₃ = min{d₁₃, d₁₄ + d₄₃} = min{6, 2 + 2} = 4,

d₁₅ = min{d₁₅, d₁₄ + d₄₅}= min{4, 2 + 1} = 3,

d₂₃ = min{d₂₃, d₂₄ + d₄₃} = min{5, 1 + 2} = 3,

d₂₅ = min{d₂₅, d₂₄-+ d₄₅} = min{5, 1 + 1} = 2,

d₃₅ = min{d₃₅, d₃₄ + d₄₅} = min{10, 2 + 1} = 3.

Изменения расстояний занесены в табл. 4

Табл. 3.

Табл. 4.

При j = 5изменений нет.

Кратчайшие расстояния между каждой парой узлов найдены. Итоговая таблица кратчайших расстояний – это табл. 4. Но необходимо найти промежуточные (внутренние) узлы для кратчайших путей.

Чтобы зафиксировать порядок, в котором появляются эти узлы, мы используем матрицу [p_i,k],в которой элемент i-ой строки и k-ro столбца указывает на первый внутренний узел в пути из V_i в V_j,. Если Р_ik = j, то кратчайший путь имеет вид V_i, V_j,..., V_k. Далее, если p_j,k = s, то кратчайший путь имеет вид V_i,V_j, V_s,..., V_k. Изначально мы полагаем P_i,k ⁼ k для всех i, k. Например, таблице 1 соответствует таблица 5.

Таблица 5. Начальная таблица промежуточных узлов

.

Таким образом, предполагается, что каждая дуга — базисная (до тех пор, пока не установлено обратное), и первым внутренним узлом на пути из Vi в V_k является сам V_k.

Во время выполнения тройственной операции над таблицей 1 мы также обновляем данные в таблице промежуточных узлов. Элементы таблицы промежуточных узлов изменяются согласно следующему правилу:

p_i,k = (3.2)

Например, когда мы присваиваем элементу d₂₅ значение d₂₁ + d₁₅ = 5, мы также полагаем

p₂₅ = p₂₁ = 1.

Когда мы присваиваем элементу d₁₄значение d₁₂+d₂₄ = 2, мы также полагаем

p₁₄ = p₁₂ = 2.

Когда мы присваиваем элементу d₁₅ значение d₁₄+d₄₅, = 2, мы также полагаем

p₁₅ = p ₁₄ = p ₁₂ = 2.

Когда мы присваиваем элементу d₂₅ значение d₂₄+d₄₅ = 2, мы также полагаем

p₂₅=p₂₄=4.

Итак, по окончании вычислений мы имеем

p₁₅ = 2, p₂₅ = 4.

Так как дуга e₄₅ — базисная, то на протяжении всех вычислений р₄₅ ⁼ 5.

p₁₅ = 2 означает, что V₂есть первый промежуточный узел на пути из V₁в V₅.

p₂₅ = 4 означает, что V₄ есть первый промежуточный узел на пути из V₂ в V₅.

p₄₅ = 5 означает, что V₅ есть первый промежуточный узел на пути из V₄в V₅.

Таким образом, мы можем выписать все промежуточные узлы на пути из V₁ в V₅ ими являются V₁, V₂, V₄и V₅.

В общем случае, чтобы найти кратчайший путь из V_g в V_t, мы находим первый промежуточный узел p_gt.

Если p_st = a, то ищем p_at =?

Если p_at = b, то ищем р_bt =?

Эти действия завершаются, когда p_zt=t. Тогда V_s , V_a , V_b ,. . . , V_z , V_t — узлы кратчайшего пути.

Элементы таблицы 5 изменяются по формулам (3.2) в то же самое время, когда элементы таблицы 1 изменяются по формулам (3.1). В конце вычислений по формулам (3.1), когда мы получаем таблицу 4 кратчайших расстояний, мы также получаем таблицу 6 промежуточных узлов, вычисленную по формулам (3.2).

Табл. 6. Таблица промежуточных узлов. Пример 2.1

Замечание 5. Несмотря на то, что таблица 1 симметрична, таблица 6 таковой не является. Для того, чтобы получить всю таблицу 6, мы должны провести все вычисления над таблицей 1, а не только половину вычислений, которые мы выполнили в примере.

Например, когда мы полагаем d₂₅ = d₅₁ + d₁₂ = 5, мы также должны выполнить присваивания p₅₂ = p₅₁ = 1.