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

Страницы работы

15 страниц (Word-файл)

Фрагмент текста работы

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

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

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

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

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

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

  θk, j, если (cik + ckj) < cij в квадратных скобках

θij =

 
  в выражении (8.5), не изменяется, если cij ≤ (cik + ckj).

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

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

хi, хY, . . ., хY, xβ, xα, xj, где хα = θij, хβ = θ, хY = θ и т. д. до хi = θiY

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

Это обстоятельство используется в гл. 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 даются в форме, позволяющей минимизировать объем вычислений при поиске кратчайших путей

Похожие материалы

Информация о работе