Алгоритм Дейкстры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оценка сложности)
Строка 39: Строка 39:
 
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
 
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
 
|-
 
|-
|style="background:#f9f9f9"|Двоичная куча
+
|style="background:#f9f9f9"|[[Двоичная куча]]
 
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
 
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
 
|-
 
|-
|style="background:#f9f9f9"|Фибоначчиева куча
+
|style="background:#f9f9f9"|[[Фибоначчиевы кучи|Фибоначчиева куча]]
 
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
 
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
 
|}
 
|}

Версия 09:22, 17 января 2012

В ориентированном взвешенном графе [math]G = (V, E)[/math], вес рёбер которого неотрицателен и определяется весовой функцией [math]w : E \rightarrow R[/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] U \gets \emptyset[/math]
Пока [math]\exists v \notin U[/math]

Пусть [math]v \notin U : 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]G = (V, E)[/math] - ориентированный взвешенный граф, вес рёбер которого неотрицателен, [math]s[/math] - стартовая вершина. Тогда после выполнения алгоритма Дейкстры [math]d(u) = \rho(s, u)[/math] для всех [math]u[/math], где [math]\rho(s, u)[/math] — длина кратчайшего пути из вершины [math]s[/math] в вершину [math]u[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции, что в момент посещения любой вершины [math]u[/math], [math]d(u) = \rho(s, u)[/math], где [math]s[/math] - стартовая вершина.

  • На первом шаге выбирается [math]s[/math], для нее выполнено: [math]d(s) = \rho(s, s) = 0[/math]
  • Пусть для [math]n[/math] первых шагов алгоритм сработал верно и на [math]n + 1[/math] шагу выбрана вершина [math]u[/math]. Докажем, что в этот момент [math]d(u) = \rho(s, u)[/math]. Для начала отметим, что для любой вершины [math]v[/math], всегда выполняется [math]d(v) \ge \rho(s, v)[/math] (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть [math]P[/math] — кратчайший путь из [math]s[/math] в [math]u[/math], [math]v[/math] — первая непосещённая вершина на [math]P[/math], [math]z[/math] — предшествующая ей (следовательно, посещённая). Поскольку путь [math]P[/math] кратчайший, его часть, ведущая из [math]s[/math] через [math]z[/math] в [math]v[/math], тоже кратчайшая, следовательно [math]\rho(s, v) = \rho(s, z) + w(zv)[/math]. По предположению индукции, в момент посещения вершины [math]z[/math] выполнялось [math]d(z) = \rho(s, z)[/math], следовательно, вершина [math]v[/math] тогда получила метку не больше чем [math]d(z) + w(zv) = \rho(s, z) + w(zv) = \rho(s, v)[/math], следовательно, [math]d(v) = \rho(s, v)[/math]. С другой стороны, поскольку сейчас мы выбрали вершину [math]u[/math], её метка минимальна среди непосещённых, то есть [math]d(u) \le d(v) = \rho(s, v) \le \rho(s, u)[/math], где второе неравенсто верно из-за ранее упомянутого определения вершины [math]v[/math] в качестве первой непосещённой вершины на [math]P[/math], то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с [math]d(u) \ge \rho(s, u)[/math], имеем [math]d(u) = \rho(s, u)[/math], что и требовалось доказать.
  • Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент [math]d(u) = \rho(s, u)[/math] для всех [math]u[/math].
[math]\triangleleft[/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 (рус.)
  • Википедия — свободная энциклопедия