Легко видеть, что кратчайшие пути от s к f будут теми же самыми один относительно другого, если все веса cjj- заменить на cj = cj -\- hi - hj, где величины h - произвольные числа, приписанные вершинам графа. Пользуясь этим фактом, Д. Кнут (в частном сообщении) показал, что, взяв h = = d (s, Xi), можно всегда получить c\j < 0. Так как расстояния d (s, х^), могут быть получены в общем случае с помощью О (п^) операций, то на самом деле (преобразуя предварительно веса) и в общем случае можно найти К кратчайших путей, используя О (Кп) операций.

заканчивает работу и дает требуемый список К кратчайших путей. Если к <с.К, положить А; = А; + 1 и вернуться к шагу 2.

Если в Li имеется более чем один кратчайший путь (скажем, h путей), то поместить в любой из них и продолжать, как и выше, до тех пор, пока увеличенное на h число путей, уже находящихся В не совпадат с К или не превысит его. Тогда алгоритм завершает работу.

Обоснование вышеприведенного алгоритма основано на очевидном факте [11], [20]: путь Р** должен быть отклонением на i-м этапе (при некотором i > 1) от одного из более коротких путей Р^, Р^, . . ., Р'~. Поэтому необходимо просто построить все кратчайшие отклонения от каждого из Р' и просмотреть их для нахождения самого короткого отклонения. Это и будет путь Р^. Следует заметить, что при к-ш итерации все кратчайшие отклонения для Р\ i = \, 2, . . ., к - 2, уже включены в Li и нужно найти только одно отклонение от Р'~ и пополнить им имеющийся список.

На шаге 3 мы полагаем с (a;f \ xi+i) = оо для тех Р\ начальные подпути которых, содержащие i вершин, совпадают с начальным г-вершинным подпутем пути Р^~. Это делается для того, чтобы не получить снова Р^ в качестве отклонения (в точке i) от пути P~, что вполне могло случиться, если бы мы действовали иначе. Так как при / <Цк - 1 вес пути Р' не больше веса пути Р^~.

Хотя на шаге 5 алгоритма каждый порожденПый путь Р) и помещается в список L, совершенно очевидно, что на к-ш итерации этот список не должен содержать более К - А -f- 1 кратчайших отклонений Р^. С вычислительной точки зрения наиболее сложным является шаг 4, где требуется О (п^) или О (п^) операций в зависимости от того, будут ли все О или с и 0. Так как этот шаг при А-й итерации выполняется раз и так как п, а число итераций равно К, то рассматриваемый алгоритм при нахождении кратчайших путей требует порядка Krf или Kn операций. Первая величина относится к графам с неотрицательными матрицами весов, а вторая - к графам с произвольными матрицами ).

6. Кратчайший путь между двумя заданными вершинами в ориентированном ациклическом графе

Методы, развитые в предыдущих разделах этой главы, приме пимы к совершенно произвольным графам. Но на практике задачу кратчайшего пути часто требуется решать для класса ориентированных ациклических графов. Такие графы возникают в методах ПЕРТ и МКП 1).

Допустим, что нужно реализовать некий большой проект, и этот проект состоит из большого числа этапов. Мы можем изобразить каждый этап вершиной некоторого графа и построить дугу от вершины Xi к вершине xj, чтобы показать, что этап i должен предшествовать этапу /. Каждой дуге приписывается некоторый вес Cij, равный минимальной задержке во времени между началом этапа i и началом этапа Пусть, например, проект представляет собой процесс строительства здания. Этап i может состоять в строительстве стен, этап ; - вставка окон, этап к - прокладка проводов в стенах и т. д. Очевидно, что в этом случае нужно провести дуги от Xi к Xj и от Xi к Xh- Но минимальный срок между началом строительства стен и вставкой окон может быть отличным от срока между строительством стен и прокладкой проводов. Если, например, оконные рамы деревянные и стены должны сначала высохнуть, а для прокладки проводов это не важно, то Cij > с^.

Совершенно очевидно, что рассматриваемый граф будет ориентированным и ациклическим. Действительно, предположение о существовании некоторого цикла, содержащего вершину Xi, приводит к (нелепому для нашей задачи) выводу о возможности повторения этапа i.

В задаче требуется найти минимальное время, необходимое для реализации проекта. Иными словами, нужно найти в графе самый длинный путь между вершиной s, изображающей начало, и вершиной t, изображающей завершение всех необходимых для реализации проекта работ. Самый длинный путь называется критическим путем, так как этапы, относящиеся к этому пути, определяют полное время реализации проекта и всякая задержка с началом выполнения любого из этих этапов приведет к задержке выполнения проекта в целом.

Сходство этой задачи с задачей о кратчайшем пути между s и t совершенно очевидно и ее можно решить, используя алгоритм

1) PERT (Project Evaluation Research Task) и СРМ Critical Path Method). Для первого метода в отечественной литературе принят термин СПУ (сетевое планирование и управление). Второй метод называют методом критического пути.- Прим. ред.

ИЗ разд. 2.1.1 (так как все 0), заменив все операции min на max. Но этот алгоритм был бы слишком неэкономичным, так как он не учитывает специально11 структуры графа. Можно применить друго11 алгоритм нахождения самого длинного пути. Этот новый алгоритм описывается ниже именно в терминах самого длинного пути, так как обычно требуется найти как раз такой путь. Задача о кратчайшем пути в ориентированном ациклическом графе также может быть решена с помош;ью приводимого алгоритма, нужно лишь все операции max заменить на min.

6.1. Алгоритм нахождения самого длинного (критического) пути в ориентированном ациклическом графе

Пусть вершины пронумерованы так, что дуга {xi, xj) всегда ориентирована от вершины Xj к вершине Xj, имеюшей больший номер. Для ациклического графа такая нумерация всегда возможна и производится очень легко. При этом начальная вершина получает номер 1, а конечная - номер п.

Присвоим вершине Xj пометку I (x ),- равную длине самого длинного пути от 1 до Xj, используя для этого соотношения

l{Xj) max [Hxi)+Cij]- (8.7)

затем присвоим пометку вершине (xj 1), применив снова формулу (8.7), и так далее до тех пор, пока последняя вершина п не получит пометку I (п). В соотношении (8.7) I (1) полагается равным нулю. Если вершина Xj помечена, то пометки I (xt) известны для всех вершин Х; 6 Г~ (xj), так как в соответствии со способом нумерации это означает, что Xt <Xj и, следовательно, вершины Xi уже помечены в процессе применения алгоритма.

Пометка / (п) равна длине самого длинного пути от 1 до п. Сами дуги, образуюш;ие путь, могут быть найдены обычным способом последовательного возвраш;ения. А именно дуга (xi, Xj) принадлежит пути тогда и только тогда, когда I (xj) - I (Xi) + -Ь Cij. Начиная с вершины Xj равной п, полагаем на каждом шаге Xj равной такой вершине (скажем, х*), для которой выполняется это последнее равенство, и так продолжаем до тех пор, пока не будет достигнута начальная вершина (т. е. пока не будет х* = 1).

Совершенно очевидно, что пометка I (Xj) вершины Xj дает длиннейший путь от 1 до Xj, т. е. самое раннее возможное начало выполнения этапа, изображаемого вершиной Xj. Таким образом, если (xj, Xj) - дуга в графе, то I (Xj) - I (х,) - Cij (неотрицательная величина, как это видно из (8.7)) дает самое большое возможное время задержки начала этапа i, не оказывающее влияния на время начала этапа Из вышесказанного видно, что если i