ВУЗ:
Составители:
Рубрика:
∞ и являются временными. Общая итерация алгоритма состоит в
следующем. Пусть p - вершина, получившая постоянную метку
l(p) на предыдущей итерации. Просматриваем все вершины с вре-
менными метками, в которые идут дуги из p, (обозначим эти вер-
шины Г(p) ) с целью уменьшения этих меток, если это возможно.
Метка l(v) вершины v
∈
Г(p) заменяется на
v,p
w)p(l
+
, если
l(v)>l(p)+w
p,v
. В этом случае говорим, что вершина v получила
свою метку l(v) из вершины p и полагаем
θ
(v)=p. Если же
l(v)
≤
l(p)+w
p,v
, то метки
θ
(v) и l(v) не изменяются на данной итера-
ции. Просматриваем все v
∈
Г(p) и для вершины u
∈
Г(p) такой, что
считаем постоянной меткой. Алгоритм
заканчивает работу, когда метка l(t) становится постоянной.
()
(,) min(,)
v Г p
lpu lpv
∈
=
(,)lpu
Обозначения: last - последняя помеченная вершина;
⎩
⎨
⎧
=
метку; временную имеет если
метку, постоянную имеет если
v,false
v,true
)v(fin
u[v] - список инцидентов для вершины v.
Алгоритм Дейкстра
нахождения расстояния между фиксиро-
ванными вершинами s и t.
for v
∈
V do l[v]:=
∞
;
for v
∈
V do fin[v]:=false;
l[s]:=0;
fin[s]:=true;
last:=s;
while not fin[t] do
begin
for v
∈
u [last] do
if not fin[v] and l[v]>l[last]+w
last,v
then
begin
l[v]:=l[last]+w
last,v
;
θ
(v):=last
end;
for v
∈
множество вершин с временными метками do
begin
определить k : l[k]=min l[v];
fin[k]:=true;
last:=k
end
end
52
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
