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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обоснование корректности работы)
(Обоснование корректности)
Строка 17: Строка 17:
  
 
== Обоснование корректности ==
 
== Обоснование корректности ==
 +
Пусть <tex>p(u, v)</tex> — длина кратчайшего пути из вершины <tex>u</tex> в вершину <tex>v</tex>. Докажем по индукции, что в момент посещения любой вершины <tex>u</tex>, <tex>d(u)=p(s,u)</tex>, где <tex>s</tex> - стартовая вершина.
  
 
== Оценка сложности ==
 
== Оценка сложности ==

Версия 01:25, 15 октября 2011

В ориентированном взвешанном графе [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]p(u, v)[/math] — длина кратчайшего пути из вершины [math]u[/math] в вершину [math]v[/math]. Докажем по индукции, что в момент посещения любой вершины [math]u[/math], [math]d(u)=p(s,u)[/math], где [math]s[/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 (рус.)
  • Википедия — свободная энциклопедия