Викиконспекты - Вклад участника [ru]

Алгоритм Дейкстры

2012-02-25T20:55:58Z

109.188.219.147:

В [[Ориентированный граф|ориентированном]] взвешенном [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] <tex>G = (V, E)</tex>, вес [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|рёбер]] которого неотрицателен и определяется весовой функцией <tex>w : E \rightarrow R</tex>, алгоритм Дейкстры находит длины кратчайших [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|путей]] из заданной [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|вершины]] <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>U</tex>, для которых уже вычислены длины кратчайших путей до них из <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \notin U</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>U</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
<code>Для всех</code> <tex>u \in V</tex>
: <tex>d[u] \gets \infty</tex>
<tex>d[s] \gets 0\</tex><br>
<tex> U \gets \emptyset</tex><br>
<code>Пока</code> <tex>\exists v \notin U</tex>
: <code>Пусть</code> <tex>v \notin U : d[v]</tex> <code> минимальный </code>
: <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</tex>, где <tex>\rho(s, u)</tex> — длина кратчайшего пути из вершины <tex>s</tex> в вершину <tex>u</tex>
|proof=
Докажем по индукции, что в момент посещения любой вершины <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) \ge \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) = \rho(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) \le d(v) = \rho(s, v) \le \rho(s, u)</tex>, где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>v</tex> в качестве первой непосещённой вершины на <tex>P</tex>, то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>d(u) \ge \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.

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

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

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных
!style="background:#f2f2f2"|Время работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|[[Двоичная куча]]
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|[[Фибоначчиевы кучи|Фибоначчиева куча]]
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Источники ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры Википедия — свободная энциклопедия]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритм Дейкстры

2012-02-25T20:52:57Z

109.188.219.147: /* Псевдокод */

В [[Ориентированный граф|ориентированном]] взвешенном [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] <tex>G = (V, E)</tex>, вес [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|рёбер]] которого неотрицателен и определяется весовой функцией <tex>w : E \rightarrow R</tex>, алгоритм Дейкстры находит длины кратчайших [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|путей]] из заданной [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|вершины]] <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>U</tex>, для которых уже вычислены длины кратчайших путей до них из <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \notin U</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>U</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
<code>Для всех</code> <tex>u \in V</tex>
: <tex>d[u] \gets \infty</tex>
<tex>d[s] \gets 0\</tex><br>
<tex> U \gets \emptyset</tex><br>
<code>Пока</code> <tex>\exists v \notin U</tex>
: <code>Пусть</code> <tex>v \notin U : d[v]</tex> <code> минимальный </code>
: <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</tex>, где <tex>\rho(s, u)</tex> — длина кратчайшего пути из вершины <tex>s</tex> в вершину <tex>u</tex>
|proof=
Докажем по индукции, что в момент посещения любой вершины <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) \ge \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) = \rho(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) \le d(v) = \rho(s, v) \le \rho(s, u)</tex>, где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>v</tex> в качестве первой непосещённой вершины на <tex>P</tex>, то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>d(u) \ge \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.

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

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

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных
!style="background:#f2f2f2"|Время работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|[[Двоичная куча]]
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|[[Фибоначчиевы кучи|Фибоначчиева куча]]
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Источники ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры Википедия — свободная энциклопедия]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]