418
правок
Изменения
Нет описания правки
'''CalcKey'''(s):
return [<tex>\min(g(s);,rhs(s)) + h(f;,s)</tex>;<tex>\min(g(s); ,rhs(s))</tex>];
'''Initialize'''():
U = <tex>\varnothing</tex>;
for s <tex>s \in S</tex>V <tex>rhs(s) = g(s) = <tex>+\infty</tex> <tex>rhs(t) = 0</tex> U.Insert(<tex>t</tex>; CalcKey(<tex>t</tex>));
'''UpdateVertex'''(u):
if (u <tex>u \ne t</tex>) t
rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (u <tex>u \in U</tex>) U
U.Remove(u);
if g(u) <tex>g(u) \ne rhs(u)</tex>rhs(u)
U.Insert(u; CalcKey(u));
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>f</tex>) OR <tex>rhs(f) <tex>\ne </tex> g(f)</tex>)
u = U.Pop();
if (g(u) > rhs(u))
g(u) = rhs(u);
for s <tex>s \in </tex> Pred(u)</tex>
UpdateVertex(s);
else
g(u) = <tex>+\infty</tex>;
for s <tex>s \in </tex> Pred(u) <tex>\cup \{u\}</tex> {u}
UpdateVertex(s);
'''ComputeShortestPath'''();
while (<tex>f \ne t</tex>)
// if (<tex>g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.
<tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (граф изменился)
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами: Обновляем результат функции <tex>c(u; v)</tex>;
'''UpdateVertex'''(u);
for s <tex>s \in U</tex>U U.Update(<tex>s</tex>; '''CalcKey'''(<tex>s</tex>));
'''ComputeShortestPath'''();
<tex>K_m = K_m + h(s_{last}, h_{start})</tex>;
<tex>s_{last} = f</tex>;
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами: Обновляем результат функции <tex>c(u; v)</tex>;
'''UpdateVertex'''(u);
'''ComputeShortestPath'''();
