418
правок
Изменения
м
→Псевдокод
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
'''Initialize'''():
//Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины. // Сортировка будет производиться по функции key(s).
U = <tex>\varnothing</tex>;
for s <tex>\in</tex> V
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
U.Insert(u; CalcKey(u));
// Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. // Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(t) OR rhs(t) <tex>\ne</tex> g(t))
