61
правка
Изменения
Нет описания правки
{{В разработке}}
В ориентированном взвешанном графе <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>)
== Обоснование корректности работы ==
{{Теорема
|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 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
