Изменения

Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость ребра <tex>(s;, s')</tex>. При этом <tex>c(s, s') = +\infty</tex> будет тогда и только тогда, когда ребра <tex>(s;, s')</tex> не существует.

'''Main'''(): '''Initialize'''(); while (true) '''ComputeShortestPathwhile'''true ComputeShortestPath(); <font color="green">//В данный момент мы знаем кратчайший путь из f в t.</font>

'''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''(v);

Теперь опишем составные элементы подробнееФункция инициализации исходного графа устанавливает для всех вершин кроме стартовой (вершины <tex>f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. '''Initialize'''(): <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины. </font> <font color="green">// Сортировка будет производиться по функции key(s).</font> U = <tex>\varnothing</tex>; '''for ''' s <tex>\in</tex> V rhs(s) = g(s) = <tex>\infty;</tex> rhs(f) = 0; U.Insert(f; , CalcKey(f));

//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, // т.е. то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex> '''CalcKey'''(s): '''return ''' [min(g(s); , rhs(s)) + h(s; , t); , min(g(s); , rhs(s))];

// Обновляет данные вершины в соответствие с данными выше определениями. // Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. '''UpdateVertex'''(u): '''if ''' u <tex>\ne</tex> f <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex> '''if ''' u <tex>\in</tex> U U.Remove(u); '''if ''' g(u) <tex>\ne</tex> rhs(u) U.Insert(u; , CalcKey(u));

// Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. // Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. '''ComputeShortestPath'''(): '''while (''' U.TopKey() < CalcKey(t) OR or rhs(t) <tex>\ne</tex> g(t)) u = U.Pop(); '''if ''' g(u) > rhs(u) g(u) = rhs(u); '''for ''' s <tex>\in</tex> Succ(u) UpdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> {u} UpdateVertex(s);

'''return''' [min(g(s),rhs(s)) + h(f,s); , min(g(s),rhs(s))];

U = <tex>\varnothing</tex>;

U.Insert(t; , CalcKey(t))

'''UpdateVertex'''(u):

U.Insert(u; , CalcKey(u))

'''Main'''():

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;

'''for''' всех ориентированных ребер <tex>(u; , v) </tex> с измененными весами: Обновляем результат функции <tex>c(u; , v)</tex>

U.Update(s; , '''CalcKey'''(s));

Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s </tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U.

Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s')</tex>, которые нужно добавить ко всем вершинам из U.

'''CalcKey'''(s): '''return ''' [min(g(s);, rhs(s)) + h(f;, s) + <tex>K_m</tex>;, min(g(s); , rhs(s))];

'''Initialize'''(): U = <tex>\varnothing</tex>;

'''for ''' s <tex>\in</tex> V

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));

'''ComputeShortestPath'''(): '''while (''' U.TopKey() < CalcKey(f) OR rhs(f) <tex>\ne</tex> g(f)) <tex>K_{old}</tex> = U.TopKey(); u = U.Pop();

'''if (''' <tex>K_{old}</tex> < '''CalcKey'''(u)) U.Insert(u; ''', CalcKey'''(u));

'''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);

'''Main'''():

'''Initialize'''(); '''ComputeShortestPath'''();

<font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;.

'''if (''' граф изменился) <tex>K_m = K_m + h(s_{last}, h_{start})</tex>; <tex>s_{last} = f</tex>; '''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''(u); '''ComputeShortestPath'''();