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