1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''for''' <tex>i \in V</tex>
v = ''null''
'''for''' <tex>j \in V</tex> <font color="green">// найдем найдём вершину с минимальным расстоянием</font>
'''if''' !used[j] '''and''' (v == ''null'' '''or''' d[j] < d[v])
v = j
|proof=
Докажем по индукции, что в момент посещения любой вершины <tex>u</tex>, <tex>d(u) = \rho(s, u)</tex>.
* На первом шаге выбирается <tex>s</tex>, для нее неё выполнено: <tex>d(s) = \rho(s, s) = 0</tex>
* Пусть для <tex>n</tex> первых шагов алгоритм сработал верно и на <tex>n + 1</tex> шагу выбрана вершина <tex>u</tex>. Докажем, что в этот момент <tex>d(u) = \rho(s, u)</tex>. Для начала отметим, что для любой вершины <tex>v</tex>, всегда выполняется <tex>d(v) \geqslant \rho(s, v)</tex> (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть <tex>P</tex> — кратчайший путь из <tex>s</tex> в <tex>u</tex>, <tex>v</tex> {{---}} первая непосещённая вершина на <tex>P</tex>, <tex>z</tex> {{---}} предшествующая ей (следовательно, посещённая). Поскольку путь <tex>P</tex> кратчайший, его часть, ведущая из <tex>s</tex> через <tex>z</tex> в <tex>v</tex>, тоже кратчайшая, следовательно <tex>\rho(s, v) = \rho(s, z) + w(zv)</tex>. По предположению индукции, в момент посещения вершины <tex>z</tex> выполнялось <tex>d(z) = \rho(s, z)</tex>, следовательно, вершина <tex>v</tex> тогда получила метку не больше чем <tex>d(z) + w(zv) = \rho(s, z) + w(zv) = \rho(s, v)</tex>, следовательно, <tex>d(v) = \rho(s, v)</tex>. С другой стороны, поскольку сейчас мы выбрали вершину <tex>u</tex>, её метка минимальна среди непосещённых, то есть <tex>d(u) \leqslant d(v) = \rho(s, v) \leqslant \rho(s, u)</tex>, где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>v</tex> в качестве первой непосещённой вершины на <tex>P</tex>, то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>d(u) \geqslant \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.
Изначально поместим в контейнер стартовую вершину <tex>s</tex>. Основной цикл будет выполняться, пока в контейнере есть хотя бы одна вершина. На каждой итерации извлекается вершина с наименьшим расстоянием <tex>d</tex> и выполняются релаксации по рёбрам из неё. При выполнении успешной релаксации нужно удалить из контейнера вершину, до которой обновляем расстояние, а затем добавить её же, но с новым расстоянием.
<br>В обычных кучах нет операции удаления произвольного элемента. При релаксации можно не удалять старые пары, в результате чего в куче может находиться одновременно несколько пар расстояние-вершина для одной вершины (с разными расстояниями). Для корректной работы при извлечении из кучи будем проверять расстояние: пары, в которых расстояние отлично от <tex>d[v]</tex> будем игнорировать. При этом асимптотика будет <tex>O(m\log{m})</tex> вместо <tex>O(m\log{n})</tex>.
== Источники информации ==
