Изменения

В ориентированном взвешанном графе {{Задача|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>U</tex>, для которых уже вычислены кратчайшие пути к ним длины кратчайших путей до них из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus notin U</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>U</tex> и производится релаксация всех исходящих из неё рёбер.

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

<code>Пока</code> <tex>\exists v \notin U</tex>: <code>Пусть</code> <tex>v \notin U</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>d[u] \gets d[v] + w [vu]</tex>: <tex>U \gets v </tex> == Обоснование корректности работы ==

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

Рассмотрим инвариант основного цикла: Докажем по индукции, что в начале каждой итерации для всех вершин момент посещения любой вершины <tex>v \in Su</tex> выполняется , <tex>d[v] (u) = \deltarho(s, vu)</tex>. '''Инициализация'''. Изначально множество * На первом шаге выбирается <tex>Ss</tex> пусто, инвариант выполняется. [[Файлдля неё выполнено:DijkstraProove.png|thumb|right|Рис. 1]]<tex>d(s) = \rho(s, s) = 0</tex>'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется * Пусть для каждой вершины, добавленной в <tex>Sn</tex>, для этого воспользуемся методом «от противного». Предположим, что первых шагов алгоритм сработал верно и на <tex>un + 1</tex> первая добавленная в шагу выбрана вершина <tex>Su</tex> вершина. Докажем, для которой равенство что в этот момент <tex>d[(u] ) = \deltarho(s, u)</tex> не выполняется. Рассмотрим ситуациюДля начала отметим, сложившуюся в начале итерации, в которой что для любой вершины <tex>uv</tex> будет добавлена в , всегда выполняется <tex>Sd(v) \geqslant \rho(s, v)</tex>. Рассмотрев (алгоритм не может найти путь короче, чем кратчайший путь из всех существующих). Пусть <tex>sP</tex> в — кратчайший путь из <tex>us</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие , <tex>u \neq sv</tex>, так как {{---}} первая непосещённая вершина на <tex>sP</tex> является первой вершиной, добавленной в <tex>Sz</tex> и в момент её добавления равенство <tex>d[u] = \delta{{---}} предшествующая ей (sследовательно, uпосещённая)</tex> выполняется. Из условия Поскольку путь <tex>u \neq sP</tex> следуеткратчайший, в частностиего часть, что ведущая из <tex>Ss</tex> не пусто. Из вершины через <tex>sz</tex> в вершину <tex>uv</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение тоже кратчайшая, следовательно <tex>d[u] = \deltarho(s, uv) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \deltarho(s, uz) + w(zv)</tex> не выполняется. Из существования пути следуетПо предположению индукции, что существует и кратчайший путь в момент посещения вершины <tex>pz</tex> из выполнялось <tex>d(z) = \rho(s, z)</tex> в , следовательно, вершина <tex>uv</tex>. Перед добавлением тогда получила метку не больше чем <tex>ud(z) + w(zv) = \rho(s, z) + w(zv) = \rho(s, v)</tex> в , следовательно, <tex>Sd(v) = \rho(s, v)</tex> путь <tex>p</tex> соединяет . С другой стороны, поскольку сейчас мы выбрали вершину из множества <tex>Su</tex> с вершиной принадлежащей множеству , её метка минимальна среди непосещённых, то есть <tex>V d(u) \setminus Sleqslant d(v) = \rho(s, v) \leqslant \rho(s, u)</tex>. Рассмотрим первую вершину , где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>yv</tex> в качестве первой непосещённой вершины на пути <tex>pP</tex> принадлежащую , то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>V d(u) \setminus Sgeqslant \rho(s, u)</tex>, и положим, что её предшествует вершина имеем <tex>x d(u) = \in S</tex>. Тогда, как видно из рис.1rho(s, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u)</tex>, что и требовалось доказать.

Утверждается*Поскольку алгоритм заканчивает работу, что в момент добавления когда все вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[y] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершинапосещены, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство этот момент <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.  Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \deltarho(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>. Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем. '''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.

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

Таким образом:Пусть <tex>n</tex> {{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%!style="background:#f2f2f2"|Структура данных для хранения множества --}} количество вершин в графе, <tex>V \setminus Sm</tex>{{---}} количество рёбер в графе.!style{| class="background:#f2f2f2wikitable"|Асимптотика времени работы

! rowspan="2" |style! colspan="background:#f9f9f93"|Наивная реализацияВремя работы|style! rowspan="background:#f9f9f92"|<tex>O(V^2+E)</tex>Описание

|stylealign="background:#f9f9f9center"|Куча ФибоначчиНаивная реализация|stylealign="background:#f9f9f9center"|<tex>O(Vn)</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{Vn}+Em)</tex>.

== Литература Источники информации ==* ''Кормен, Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', — 2-е издание. Пер. с англизд. — М.:Издательский дом "Вильямс"«Вильямс», 20102007. — 1296 с.: ил. — Парал. тит. англ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]