8 Сетевые графики. Алгоритм поиска критического пути.

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

Семантика задачи. Сопоставим каждой дуге работу. Вес дуги - время выполнения работы.

Вершине сопоставим событие, состоящее в том, что все работы, приписанные заходящим в нее дугам, выполнены, и можно начинать все работы, приписанные исходящим дугам. Граф с такой трактовкой называется диаграммой ПЕРТ (от Program Evaluation and Review Technique) или сетевым графиком.

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

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

Однако задано добавочное условие на граф задачи: в нем нет контуров.

Добавочные условия могут потребовать проверки их выполнения и усложнить алгоритм, но можно использовать эти условия и для сокращения алгоритма, что мы и сделаем.

Справедлива следующая теорема: если в графе нет контуров, то его вершины можно перенумеровать таким образом, что всякая дуга идет из вершины с меньшим номером в вершину с большим номером и при этом возможна последовательная нумерация вершин от 1 до n=|A|.

Будем использовать широко распространенный в программировании прием для сокращения решения комбинаторных задач - вначале тратятся добавочные усилия на предварительное упорядочение, затем в упорядоченном множестве более просто находят решение.

1. Упорядочим множество вершин так, чтобы любая дуга исходила

из вершины с меньшим номером и заходила в вершину с большим номе-

ром. Это можно сделать так: присвоим начальной вершине номер 1. Всем вершинам A', связанным с начальной по исходящим дугам, сопоставим номера от 2 до |А’|. После этого проверим номера этих вершин на выполнение условия. Для любой пары вершин, где условие не выполняется, переставим номера вершин. Затем рассматриваются вершины, связанные по исходящим дугам с множеством А’ и т. д.

2. Присвоим всем вершинам вес l(i)=0.

3. Последовательно для вершин 1, 2, 3, ... проведем пересчет весов

по формуле l(i) = max (l(i), l(j)+Cji ), где максимум берется по всем вершинам j, из которых есть дуги в вершину i. Это можно сделать, так как ко времени пересчета вершины i веса всех вершин j вычислены раньше, ибо i>j.

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

4. Как и в алгоритме Дейкстры, выделим обратным ходом искомый путь.