40. Нахождение кратчайшего расстояния между двумя вершинами ориентированного бесконтурного графа. Временная сложность алгоритма

 

Зубова про 40 сказала вот что: «то же самое, что и в Дейкстре, только путь возможен только от вершин с меньшим номером, к вершинам с большим».

 

Ориентированный граф <V, E> , где V = {v1, ... , vn}, и для произвольной дуги < vi, vj > принадл. E имеем i < j. Этот граф определен списками инцидентности ПРЕДШ[v], v принадлV.

Результаты: Расстояния от v1 до всех вершин графа: 
 

D[vi] = d(v1, vi), i = 1, ..., n.

 

1 begin

2 D[v1] := 0;

3 for j := 2 to n do D[vj] := T;

4 for j := 2 to n do

5 for vi принадл. ПРЕДШ [vj] do D[vj] := min(D[vj]), D[vi] + A[vi, vj])

6 end 
  

Нетрудно доказать индукцией по j, что после выполнения цикла 4 для некоторого значения j выполняется равенство D[vi] = d(v1, vi), i = 1, ..., j. Достаточно воспользоваться тем фактом, что все промежуточные вершины кратчайшего пути из v1 в vi имеют номера меньше j.

Сложность алгоритма порядка O(m), так как каждая дуга <vi, vj> анализируется а строке 5 в точности один раз.

Описанные алгоритмы находят применения, в частности, в методах управления выполнением проекта, называемых PERT  (Project Evaluation and Review Technique) или CPM  (Critical Path Method). Эти методы основываются на построении графа (сети PERT или сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач.

Кроме этого, мы предполагаем, что для произвольных дуг этого графа  < u, v >и < v, t >задача, изображаемая дугой < u, v >, должна быть закончена перед началом решения задачи, изображаемой дугой áv, tñ .

Легко заметить, что такой граф должен быть бесконтурным. Нашей задачей является нахождение самого длинного пути из вершины s, соответствующей началу проекта, до вершины t, соответствующей его окончанию. Такой путь называется критическим путем. Его длина определяет время, необходимое для реализации всего проекта. Очевидно, что задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса a(u, v), где u (p) v, на обратный.