|
|
| Строка 16: |
Строка 16: |
| | : <tex>U \gets v </tex> | | : <tex>U \gets v </tex> |
| | | | |
| − | == Обоснование корректности работы == | + | == Обоснование корректности == |
| − | {{Теорема
| |
| − | |statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
| |
| − | |proof=
| |
| − | Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>
| |
| − | | |
| − | '''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.
| |
| − | | |
| − | [[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
| |
| − | '''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <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 \delta(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>.
| |
| − | }}
| |
| | | | |
| | == Оценка сложности == | | == Оценка сложности == |
В ориентированном взвешанном графе [math]G = (V, E)[/math], вес рёбер которого неотрицателен и определяется весовой функцией [math]w(uv) \geqslant 0[/math], Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины [math]s[/math] до всех остальных.
Алгоритм
В алгоритме поддерживается множество вершин [math]U[/math], для которых уже вычислены кратчайшие пути к ним из вершины [math]s[/math]. На каждой итерации основного цикла выбирается вершина [math] u \notin U[/math], которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина [math]u[/math] добавляется в множество [math]U[/math] и производится релаксация всех исходящих из неё рёбер.
Псевдокод
Для всех [math]u \in V[/math]
- [math]d[u] \gets \infty[/math]
[math]d[s] \gets 0\[/math]
Пока [math]\exists v \notin U[/math]
-
Пусть [math]v \notin U[/math] — вершина с минимальным [math]d[v][/math]
-
Для всех [math]u \notin U[/math] таких, что [math]vu \in E[/math]
-
если [math] d[u] \gt d[v] + w(vu)[/math] то
- [math]d[u] \gets d[v] + w (vu)[/math]
- [math]U \gets v [/math]
Обоснование корректности
Оценка сложности
Основной цикл выполняется [math]V[/math] раз. Релаксация выполниться всего [math]E[/math] раз. В реализации алгоритма присутствует функция выбора вершины с минимальным значением [math]d[/math], асимптотика её работы зависит от реализации.
Таким образом:
| Структура данных
|
Время работы
|
| Наивная реализация
|
[math]O(V^2+E)[/math]
|
| Двоичная куча
|
[math]O(E\log{V})[/math]
|
| Куча Фибоначчи
|
[math]O(V\log{V}+E)[/math]
|
Источники
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Википедия — свободная энциклопедия
