Сетевые графики

ОПРЕДЕЛЕНИЕ 34. Сетевым графиком называется ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком.

Сетевые графики широко используются при организации производства сложных работ. Вершинами являются состояния объекта, дугами – переходы из состояния в состояние, весами – сроки выполнения отдельных этапов работ. Особенно широко сетевые графики используются в строительстве. Естественным является вопрос о минимальных сроках производства. Для этого должны быть выполнены все виды работ. Поэтому минимальный срок равен максимальной длине (весу) пути из истока в сток. Этот путь называется критическим. В реальном производстве задержки работ, расположенных на критическом пути, приводят к срыву сроков производства. Если интерпретировать сетевой график как сеть дорог с односторонним движением, а веса как расстояния, то можно искать кратчайший путь от источника к стоку. Такую задачу мы уже рассматривали, в частности, был описан алгоритм Дейкстры. Для сетевого графика решение, возможно, проще. Кратчайший путь мы здесь также называем критическим.

Алгоритм построения критического пути начинается с правильной нумерации вершин графа (она возможна, поскольку граф ациклический). При этом исток приобретает номер 1, а сток – номер p. Пусть Г^-1(i)= , т.е. это множество номеров вершин, непосредственно предшествующих i -й вершине.

Далее формируются пометки вершин s (i) следующим образом. s (1)=0,

Для i от 2 до p

Нц s (i)= (если ищется длиннейший путь),

s (i)= (если ищется кратчайший путь) Кц.

В результате получаем s (p) – вес критического пути. Для восстановления самого пути (или путей) можно сохранять номера предшественников, на которых достигается максимум (минимум) в цикле. Реализовывать этот алгоритм также целесообразно в виде таблицы.