Изменения

В [[Ориентированный граф{{Задача|ориентированном]] взвешенном [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] definition=Для заданного взвешенного графа <tex>G = (V, E)</tex>, вес [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|рёбер]] которого неотрицателен и определяется весовой функцией <tex>w : E \to \mathbb{R}</tex>, алгоритм Дейкстры находит длины кратчайших [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|путей]] найти кратчайшие пути из заданной [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|вершины]] <tex>s</tex> до всех остальныхвершин. Веса всех рёбер неотрицательны.}}

<code>Для всех</code> '''func''' dijkstra(s)''':''' '''for''' <tex>u v \in V</tex> : d[v] = <tex>d[u] \gets \infty</tex><tex> used[v] = ''false'' d[s] \gets = 0\</tex><br> '''for''' <tex> U i \gets \emptysetin V</tex><br><code>Пока</code> v = ''null'' '''for''' <tex>j \exists v \notin Uin V</tex>: <codefont color="green">Пусть// найдём вершину с минимальным расстоянием</codefont> '''if''' !used[j] '''and''' (v == ''null'' '''or''' d[j] <tex>d[v]) v \notin U : = j '''if''' d[v]== </tex> <code> минимальный \infty</codetex> '''break''' used[v] = ''true'' '''for''' e : исходящие из ''v'' рёбра <codefont color="green">Для всех</code> <tex>u \notin U</tex> <code>такихпроизведём релаксацию по всем рёбрам, чтоисходящим из ''v''</code> <tex>vu \in E</texfont>:: <code>если</code> <tex> '''if''' d[uv] > + e.len < d[ve.to] + w(vu)</tex> <code>то</code>::: <tex> d[ue.to] \gets = d[v] + w (vu)</tex>: <tex>U \gets v </tex>e.len

* На первом шаге выбирается <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) \ge 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) \le leqslant d(v) = \rho(s, v) \le leqslant \rho(s, u)</tex>, где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>v</tex> в качестве первой непосещённой вершины на <tex>P</tex>, то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>d(u) \ge geqslant \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.

Основной цикл выполняется <tex>V</tex> раз. Релаксация выполнится всего <tex>E</tex> раз. В реализации алгоритма присутствует функция выбора вершины с минимальным значением <tex>d</tex>, асимптотика её и релаксация по всем рёбрам для данной вершины. Асимптотика работы зависит от реализации.

Таким образом:Пусть <tex>n</tex> {{---}} количество вершин в графе, <tex>m</tex> {{---}} количество рёбер в графе. {| borderclass="1wikitable" cellpadding|-! rowspan="52" cellspacing="0" style="text-align:center" width=30%|!stylecolspan="background:#f2f2f23"|Структура данных Время работы!stylerowspan="background:#f2f2f22"|Время работыОписание|-! Поиск минимума! Релаксация! Общее

|stylealign="background:#f9f9f9center"|Наивная реализация|stylealign="background:#f9f9f9center"|<tex>O(Vn)</tex>| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(n^2+Em)</tex>| align="center" | <tex>n</tex> раз осуществляем поиск вершины с минимальной величиной <tex>d</tex> среди <tex>O(n)</tex>непомеченных вершин и <tex>m</tex> раз проводим релаксацию за <tex>O(1)</tex>. Для плотных графов (<tex>m \approx n^2</tex>) данная асимптотика является оптимальной.

|stylealign="background:#f9f9f9center"|[[Двоичная куча]]|stylealign="background:#f9f9f9center"|<tex>O(E\log{Vn})</tex>| align="center" | <tex>O(\log{n})</tex>| align="center" | <tex>O(m\log{n})</tex>| align="center" | Используя двоичную кучу можно выполнять операции извлечения минимума и обновления элемента за <tex>O(\log{n})</tex>. Тогда время работы алгоритма Дейкстры составит <tex>O(n\log{n} + m\log{n}) = O(m\log{n})</tex>.

|stylealign="background:#f9f9f9center"|[[Фибоначчиевы кучи|Фибоначчиева куча]]|stylealign="background:#f9f9f9center"|<tex>O(V\log{Vn})</tex>| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(n\log{n} + m)</tex>| align="center" | Используя Фибоначчиевы кучи можно выполнять операции извлечения минимума за <tex>O(\log{n})</tex> и обновления элемента за <tex>O(1)</tex>. Таким образом, время работы алгоритма составит <tex>O(n\log{n}+Em)</tex>.

На практике удобно использовать стандартные контейнеры (например, '''std::set''' или '''std::priority_queue''' в C++). <br>При реализации необходимо хранить вершины, которые упорядочены по величине <tex>d</tex>, для этого в контейнер можно помещать пару {{---}} расстояние-вершина. В результате будут храниться пары, упорядоченные по расстоянию.  Изначально поместим в контейнер стартовую вершину <tex>s</tex>. Основной цикл будет выполняться, пока в контейнере есть хотя бы одна вершина. На каждой итерации извлекается вершина с наименьшим расстоянием <tex>d</tex> и выполняются релаксации по рёбрам из неё. При выполнении успешной релаксации нужно удалить из контейнера вершину, до которой обновляем расстояние, а затем добавить её же, но с новым расстоянием.<br>В обычных кучах нет операции удаления произвольного элемента. При релаксации можно не удалять старые пары, в результате чего в куче может находиться одновременно несколько пар расстояние-вершина для одной вершины (с разными расстояниями). Для корректной работы при извлечении из кучи будем проверять расстояние: пары, в которых расстояние отлично от <tex>d[v]</tex> будем игнорировать. При этом асимптотика будет <tex>O(m\log{m})</tex> вместо <tex>O(m\log{n})</tex>. == Источники информации ==* ''Кормен, Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', — 2-е издание. Пер. с англизд. — М.:Издательский дом "Вильямс"«Вильямс», 20102007. — 1296 с.: ил. — Парал. тит. англ459. — ISBN 978-5-84598489-0857-5 (рус4* [http://e-maxx.)ru/algo/dijkstra MAXimal :: algo :: Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры]* [httphttps://ru.wikipedia.org/wiki/Алгоритм_Дейкстры Википедия — свободная энциклопедияАлгоритм Дейкстры]* [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Wikipedia — Dijkstra's algorithm]