![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм отыскания критического пути
Опишем алгоритм для нахождения критического пути в сетевом графике. В процессе работы алгоритма для каждой вершины 1°. Правильная нумерация сети. Нумерация вершин сети называется правильной, если номер начала любой дуги сети меньше, чем номер ее конца. Правильная нумерация ациклической сети всегда возможна и производится следующим образом. Нумеруем начальную вершину сети нулем и удаляем ее из сети вместе со всеми выходящими из нее дугами. В получающейся сети непременно образуются вершины, не имеющие входящих дуг (это следует из ацикличности), которые назовем вершинами первого ранга и занумеруем их числами 1, 2, … Далее удалим все вершины первого ранга и выходящие из них дуги. Появившиеся вершины без входящих дуг назовем вершинами второго ранга и дадим им очередные номера. Этот процесс продолжается до тех пор, пока не будут занумерованы все вершины сети. 2°. Расстановка отметок. Пусть сеть правильно занумерована. Для каждой вершины – полагаем – просматриваем вершины в порядке их номеров и для
где максимум берется по всем вершинам По окончании процесса вычисления отметок величина 3°. Построение критического пути. Начиная с вершины-конца, последовательно находим дуги
|