Кратчайшие пути. Кратчайший путь между двумя заданными вершинами s и t. Кратчайшие пути между всеми парами вершин

Если c_ij <0, то в графе G существует цикл отрицательного веса, содержащий вершину x_i, и решения нет. Останов.

(б)  Если все c_ij ≥ 0 и k = n, то получено решение. Матрица [c_ij] дает длины всех кратчайших путей.  Останов.

(в)  Если все c_ij ≥ 0, но k < n, то вернуться к шагу 2.

Доказательство оптимальности ответа, полученного с помощью этого алгоритма, чрезвычайно простое [21], [27], и мы предоставляем его читателю. Основная операция алгоритма, определяемая соотношением (8.5), называется трехместной операцией. Она имеет разнообразные применения в задачах той же природы, что и задача о кратчайшем пути. Такие задачи обсуждаются в последующих разделах.

Сами кратчайшие пути можно найти по их длинам с помощью рекурсивной процедуры, подобной той, которая выше определялась соотношением (8.2). С другой стороны, можно использовать технику, предложенную Ху [21], для записи информации о самих путях (наряду с информацией о длинах путей). Этот последний метод аналогичен использованному в разд. 2.2.1 и особенно полезен в тех случаях, когда требуется найти в графе цикл отрицательного веса (если такой существует). В этом методе в дополнение к матрице весов С хранится и обновляется вторая (n x n)-матрица Θ = [θ_ij]. Элемент θ_ij - указывает вершину, непосредственно предшествующую вершине x_j в кратчайшем пути от x_i к x_j. Матрице Θ присваиваются начальные значения θ_ij = x_i для всех x_i и x_j.

В соответствии с (8.5) на шаге 3 алгоритма обновление матрицы происходит так:

  θ_k, _j, если (c_ik + c_kj) < c_ij в квадратных скобках

θij =

  в выражении (8.5), не изменяется, если c_ij ≤ (c_ik + c_kj).

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

Таким образом, кратчайший путь между двумя вершинами x_i и x_j дается следующей последовательностью   вершин:

х_i, х_Y, . . ., х_Y, x_β, x_α, x_j, где х_α = θ_ij, х_β = θ_iα, х_Y = θ_iβ и т. д. до х_i = θ_iY

Здесь следует отметить, что если всем c_ij придать начальные значения ∞ (а не 0), то конечное значение величины c_ii будет равно весу цепи, проходящей через вершину x_i. Легко также видеть, что, исходя из структуры матрицы Θ, полученной в процессе той итерации, когда элемент c_ii становится отрицательным, легко найти цикл отрицательного веса, соответствующий этому элементу.

Это обстоятельство используется в гл. 11 при реализации основного шага в алгоритме поиска в графе потока минимальной стоимости. Оно оказывается также полезным и во многих других приложениях (об этом говорится в следующем разделе).

4. Обнаружение циклов отрицательного веса

Задача выявления циклов отрицательного веса в произвольном графе важна как сама по себе, так и в качестве основного шага в более сложных алгоритмах (см. разд. 4.1 ниже и гл. 11). В настоящем разделе эта задача обсуждается несколько более подробно, чем в предыдущем.

В разд. 3.1 отмечалось, что алгоритм Флойда нахождения кратчайших путей между всеми парами вершин может быть использован и для обнаружения в графе циклов отрицательного веса. Кроме того, в тех случаях, когда в графе имеется вершина s, из которой достижимы все остальные вершины этого графа, для нахождения циклов отрицательного веса можно также использовать алгоритм из разд. 2.2.1 (как это указывается на шаге 3(b)). Если не все вершины графа G достижимы из s (например, когда G является неориентированным графом, составленным не менее чем из двух связных компонент), то алгоритм разд. 2.2.1 завершит работу (как и должно быть) при следующем распределении пометок: у вершин из компоненты, содержащей s, пометки конечные, а пометки вершин в других компонентах равны ∞. В этом случае циклы отрицательного веса, лежащие в других компонентах, не будут обнаружены. Тем не менее во многих важных приложениях алгоритма обнаружения цикла отрицательного веса (см., например, гл. 11, разд. 5) всегда имеется в распоряжении вершина s, из которой достижимы все остальные вершины. В таких случаях алгоритм из разд. 2.2.1 при поиске циклов отрицательного веса предпочтительней с вычислительной точки зрения, чем алгоритм Флойда.

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