Изменения
Нет описания правки
В ориентированном взвешенном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) : E \geqslant 0rightarrow R</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной заданной вершины <tex>s</tex> до всех остальных.
== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>U</tex>, для которых уже вычислены кратчайшие пути к ним длины кратчайших путей до них из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \notin U</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>U</tex> и производится релаксация всех исходящих из неё рёбер.
== Псевдокод ==
<code>Пока</code> <tex>\exists v \notin U</tex>
: <code>Пусть</code> <tex>v \notin U: d[v]</tex> <code> — вершина с минимальнымминимальный </code> <tex>d[v]</tex>
: <code>Для всех</code> <tex>u \notin U</tex> <code>таких, что</code> <tex>vu \in E</tex>
:: <code>если</code> <tex> d[u] > d[v] + w(vu)</tex> <code>то</code>
== Обоснование корректности ==
Пусть <tex>\rho(u, v)</tex> — длина кратчайшего пути из вершины <tex>u</tex> в вершину <tex>v</tex>. Докажем по индукции, что в момент посещения любой вершины <tex>u</tex>, <tex>d(u) = \rho(s, u)</tex>, где <tex>s</tex> - стартовая вершина.
* Первая вершина - стартовая <tex>d(s) = l\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) \ge \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>k</tex>, такое что <tex>\rho(s, k) + w(kv) < \rho(s, z) + w(zv)</tex> то <tex>z</tex> не принадлежит <tex>P</tex>). Следовательно, <tex>d(v) = \rho(s, v)</tex>. С другой стороны, поскольку сейчас мы выбрали вершину <tex>u</tex>, её метка минимальна среди непосещённых, то есть <tex>d(u) \le d(v) = \rho(s, u) \le \rho(s, v)</tex>. Комбинируя это с <tex>d(u) \ge \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.
