61
правка
Изменения
Новая страница: «{{В разработке}} == Алгоритм == В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер кот…»
{{В разработке}}
== Алгоритм ==
В ориентированном взвешанном графе <tex>G = (V, E)</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 \neq \emptyset</tex>
'''do''' <tex>u \gets</tex> ''Extract_Min''(<tex>Q</tex>)
<tex>s \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''Relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)
== Обоснование корректности работы ==
== Оценка сложности ==
== литература ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
== Алгоритм ==
В ориентированном взвешанном графе <tex>G = (V, E)</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 \neq \emptyset</tex>
'''do''' <tex>u \gets</tex> ''Extract_Min''(<tex>Q</tex>)
<tex>s \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''Relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)
== Обоснование корректности работы ==
== Оценка сложности ==
== литература ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
