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

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

Допустим, что нужно реализовать некий большой проект, и этот проект состоит из большого числа этапов. Мы можем изобразить каждый зтап вершиной некоторого графа и построить дугу от вершины к вершине чтобы показать, что этап должен предшествовать этапу Каждой дуге приписывается некоторый вес равный минимальной задержке во времени между началом этапа и началом этапа Пусть, например, проект представляет собой процесс строительства здания. Этап может состоять в строительстве стен, этап вставка окон, зтап к — прокладка проводов в стенах и т. д. Очевидно, что в этом случае нужно провести дуги от и от Но минимальный срок между началом строительства стен и вставкой окон может быть отличным от срока между строительством стен и прокладкой проводов. Если, например, оконные рамы деревянные и стены должны сначала высохнуть, а для прокладки проводов это не важно, то

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

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

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

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