3 0 3 5 6 ? 4 [3,4,5]
3 0 3 5 6 ? 4 [3,4,5]
4 0 3 5 6 9 4 [4,5]
5 0 3 5 6 7 4 [5]
procedure Distance;
{A, D, s - глобальные}
var v,u: integer;T:set of 1..N;
begin{инициализация D}
for v?V do D[v]:=A[s,v];
D[s]:=0; T:=[1..N]-[s];
{основной цикл}
while T<>[ ] do begin
u:=<то значение l, при котором достигается min(D[l])>;
T:=T-[u]; l?T
for v?T do D[v]:=min(D[v],D[u]+A[u,v]);
end;
end;
Время работы алгоритма пропорционально N2.
3.6.3. Пути в бесконтурном графе
Дано. Ориентированный граф G=<V,E> без контуров, веса дуг произвольны. Результат. Массив кратчайших расстояний(длин) D от фиксированной вершины до всех остальных. Утверждение. В произвольном бесконтурном графе вершины можно перенумеровать так, что для каждой дуги <i,j> номер вершины i будет меньше номера вершины j.
Пример.
Введем следующие структуры данных:
• массив NumIn, NumIn[i] определяет число дуг, входящих в вершину с номером
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
