Изменения

Перейти к: навигация, поиск

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

1392 байта добавлено, 07:29, 6 декабря 2010
Нет описания правки
{{В разработке}}
 
В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.
== Алгоритм ==
В ориентированном взвешанном графе алгоритме поддерживается множество вершин <tex>G = (V, E)S</tex>, вес рёбер которого неотрицателен, Алгоритм Дейкстры находит длинну кратчайшего для которых уже вычислены кратчайшие пути к ним из одной вершины <tex>s</tex> до . На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех остальныхисходящих из неё рёбер
== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex> <tex>d[s] \gets 0</tex> <tex>S \gets \emptyset</tex> <tex>Q \gets V[G]</tex> '''while''' <tex>Q V \setminus S \neq \emptyset</tex> '''do''' <tex>u \gets</tex> ''Extract_Minargmin''(<tex>Qv : v \in V \setminus S, d[v]</tex>) <tex>s S \gets S \cup \{u\}</tex> '''for''' <tex>(uv) \in E</tex> '''do''' ''Relaxrelax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>) 
== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V(G)</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, u)</tex>
 
'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.
 
'''Сохранение'''.
}}
 
== Оценка сложности ==
== литература Литература ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
61
правка

Навигация