418
правок
Изменения
Нет описания правки
{{Определение
|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам:
<tex>rhs(s) =
\begin{cases}
{{Определение
|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>
}}
{{Определение
|definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>
}}
{{Определение
|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>
}}
Основная функция, описывающая алгоритм
<font color="green">// В данный момент мы знаем кратчайший путь из f в t.</font>
Ждем каких-либо изменений графа.
'''for''' всех ориентированных ребер (u, v) с измененными весами:
Обновляем результат функции c(u, v)
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
<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.Insertinsert(f, CalcKeycalcKey(f))
Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex>
'''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди 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.Removeremove(u)
'''if''' g(u) <tex>\ne</tex> rhs(u)
U.Insertinsert(u, CalcKeycalcKey(u))
Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''if''' g(u) > rhs(u)
g(u) = rhs(u)
'''for''' <tex>s </tex> <tex>\in</tex> Succ(u)
UpdateVertex(s)
'''else'''
g(u) = <tex>+\infty</tex>
'''for''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex> UpdateVertexupdateVertex(s)
=== Асимптотика ===
При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения.
'''return''' [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
U = <tex>\varnothing</tex>
'''for''' s <tex>\in</tex> V
rhs(s) = g(s) = <tex>+\infty</tex>
rhs(t) = 0
U.Insertinsert(t, CalcKeycalcKey(t))
'''function''' 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.Removeremove(u)
'''if''' g(u) <tex>\ne</tex> rhs(u)
U.Insertinsert(u, CalcKeycalcKey(u))
'''function''' ComputeShortestPath(): '''while''' U.TopKeytopKey() < CalcKeycalcKey(f) or rhs(f) <tex>\ne</tex> g(f) u = U.Poppop()
'''if''' (g(u) > rhs(u))
g(u) = rhs(u)
'''for''' s <tex>\in</tex> Pred(u)
'''else'''
g(u) = <tex>+\infty</tex>
'''for''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> {u} UpdateVertexupdateVertex(s)
'''while''' <tex>f \ne t</tex>
<font color="green">// '''if''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
'''for''' всех ориентированных ребер <tex>(u, v)</tex> с измененными весами:
Обновляем результат функции <tex>c(u, v)</tex>
=== Асимптотика ===
=== Псевдокод ===
'''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>K_m</tex>, min(g(s), rhs(s))]
U = <tex>\varnothing</tex>
<tex>K_m = 0</tex>
rhs(s) = g(s) = <tex>+\infty</tex>
rhs(t) = 0
U.Insertinsert(t, CalcKey(t))
'''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.Removeremove(u)
'''if''' g(u) <tex>\ne</tex> rhs(u)
U.Insertinsert(u, CalcKeycalcKey(u))
'''if''' <tex>K_{old}</tex> < CalcKeycalcKey(u) U.Insertinsert(u, CalcKeycalcKey(u))
'''if''' (g(u) > rhs(u))
g(u) = rhs(u)
'''for''' <tex>s </tex> <tex>\in</tex> Pred(u) UpdateVertexupdateVertex(s)
'''else'''
g(u) = <tex>+\infty</tex>
'''for''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\} </tex> UpdateVertexupdateVertex(s)
<tex>s_{last} = f</tex>
<font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>
<tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex>
'''for''' всех ориентированных ребер (u, v) с измененными весами:
Обновляем результат функции c(u, v)
=== Асимптотика ===
