ОПРЕДЕЛЕНИЕ 34.Сетевым графикомназывается ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком.
Сетевые графики широко используются при организации производства сложных работ. Вершинами являются состояния объекта, дугами – переходы из состояния в состояние, весами – сроки выполнения отдельных этапов работ. Особенно широко сетевые графики используются в строительстве. Естественным является вопрос о минимальных сроках производства. Для этого должны быть выполнены все виды работ. Поэтому минимальный срок равен максимальной длине (весу) пути из истока в сток. Этот путь называется критическим. В реальном производстве задержки работ, расположенных на критическом пути, приводят к срыву сроков производства. Если интерпретировать сетевой график как сеть дорог с односторонним движением, а веса как расстояния, то можно искать кратчайший путь от источника к стоку. Такую задачу мы уже рассматривали, в частности, был описан алгоритм Дейкстры. Для сетевого графика решение, возможно, проще. Кратчайший путь мы здесь также называем критическим.
Алгоритм построения критического пути начинается с правильной нумерации вершин графа (она возможна, поскольку граф ациклический). При этом исток приобретает номер 1, а сток – номер p. Пусть Г-1(i)= , т.е. это множество номеров вершин, непосредственно предшествующих i-й вершине.
Далее формируются пометки вершин s(i) следующим образом. s(1)=0,
Для i от 2 до p
Нц s(i)= (если ищется длиннейший путь),
s(i)= (если ищется кратчайший путь) Кц.
В результате получаем s(p) – вес критического пути. Для восстановления самого пути (или путей) можно сохранять номера предшественников, на которых достигается максимум (минимум) в цикле. Реализовывать этот алгоритм также целесообразно в виде таблицы.