Компьютерные сети. Лабораторные работы


Алгоритм Дейкстры


Более эффективным алгоритмом для решения данной задачи является алгоритм Дейкстры , применяемый в том случае, если веса всех дуг неотрицательны [Липский,1988]. Исходная информация и результаты работы аналогичны предыдущему алгоритму.

For v I V do D [ v ]:= A [ s , v ];

D[s]:=0; T:=V\{s};

While T?0 do

begin

u:=Произвольная вершина rIT , такая, что D[ r ]= min {D[p]:pIT};

T:=T\{u};

For vIT do D[v]:=min(D[v],D[v]+A[u,v])

end

Механизм работы алгоритма Дейкстры представлен на следующем рисунке [ Бурковский , Холопкина , Райхель , Кравец,1996]:




- Начало -  - Назад -  - Вперед -



Книжный магазин