Пути в бесконтурной сети
Займемся теперь вторым случаем, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O(n 2 ), а именно случаем, когда граф является бесконтурным (теперь веса дуг могут быть произвольными). При описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером.
Исходной информацией для алгоритма поиска расстояний D[v 1 ]= d (v 1 ,v i ), i=1,..., n от источника v 1 до всех заданных вершин в бесконтурном графе является ориентированный граф (V,Е), где V={v 1 ,..., v n }, и для произвольной дуги < v i ,v j >IЕ имеем i < j . Граф опре-деляется линейными списками Предш [ v ], vIV [Липский,1988].
D[v 1 ]:=0;
For j:=2 to n do D[v j ]:= ? ;
For j:=2 to n do
For v i I Предш [v j ] do D[v j ]:=min(D[v j ],D[v i ]+A[v i ,v j ])
