Изменения

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

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

'''Dijkstrafunc'''dijkstra(s)''':''' '''for''' <tex>G</tex>, <tex>wv \in V</tex>, <tex>s</tex>) d[v] = <tex>d \gets \infty</tex> <tex> used[v] = ''false'' d[s] \gets = 0</tex> '''for''' <tex>S i \gets \emptysetin V</tex> v = ''null'while' '''for''' <tex>j \in V \setminus S \neq \emptyset</tex> <font color="green">// найдём вершину с минимальным расстоянием</font> '''doif''' !used[j] '' 'and'argmin''(v == ''null'' '''or''' d[j] <tex>d[v : ]) v \in V \setminus S, = j '''if''' d[v]== </tex>) <tex>S \gets S \cup \{u\}infty</tex> '''break''for' used[v] = ''true'' <tex>(uv) \in E</tex> '''dofor''' e : исходящие из ''relaxv''(рёбра <texfont color="green">u</tex>/ произведём релаксацию по всем рёбрам, <tex>исходящим из ''v''</texfont>, '''if''' d[v] + e.len <tex>w</tex>)d[e.to] d[e.to] = d[v] + e.len

== Обоснование корректности работы ==

|statement=После окончания работы Пусть <tex>G = (V, E)</tex> {{---}} ориентированный взвешенный граф, вес рёбер которого неотрицателен, <tex>s</tex> {{---}} стартовая вершина.Тогда после выполнения алгоритма Дейкстры для всех вершин <tex>d(u ) = \in Vrho(Gs, u)</tex> будет выполняться равенство для всех <tex>d[u] = </tex>, где <tex>\deltarho(s, u)</tex> {{---}} длина кратчайшего пути из вершины <tex>s</tex> в вершину <tex>u</tex>

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

'''Сохранение'''*Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент <tex>d(u) = \rho(s, u)</tex> для всех <tex>u</tex>.

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