418
правок
Изменения
м
|author=Свен Кёниг
|author=Свен Кёниг
→Асимптотика
{{Теорема
|about=О монотонности изменения ключей
|statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди , монотонно не убывают.
}}
{{Теорема
|about=О необратимой насыщенности
|statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной.
}}
{{Теорема
|statement=После выполнения функции '''ComputeShortestPath''' можно проследить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + с(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>.
}}
