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