Изменения
Нет описания правки
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф ]] <tex> G(V, E) </tex>. Даны вершины <tex>s_{start}</tex> и <tex>s_{goal}</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>
=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.
Обозначим множество <tex>Succ(s) \in V</tex> как множество вершин, исходящих из вершины <tex>s</tex>.
Аналогично множество <tex>Pred(s) \in V</tex> как множество вершин, входящих в вершину <tex>s</tex>.
Функция <tex>0 \leqslant сc(s, s') \leqslant +\infty</tex> будет возвращать стоимость перехода из вершины <tex>s</tex> в вершину <tex>s'</tex>. При этом <tex>s' \in Succ(s)</tex>. Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}</tex> до <tex>s</tex>.
Если <tex>s = s_{start}</tex>
}
//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
'''CalcKey'''(s):
{
}
// Функция неоднократно перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''ComputeShortestPath'''():
{
U.Update(<tex>s</tex>; '''CalcKey'''(<tex>s</tex>));
ComputeShortestPath();
{{Теорема
|author=Свен Кёниг
|about=Об устойчивой насыщенности вершин
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она перенасыщена.
}}
==Ссылки==
