188
правок
Изменения
Нет описания правки
== Алгоритм ==
В [[Ориентированный граф|ориентированном]] взвешенном [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] <tex>G = (V, E)</tex>, вес [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|рёбер]] которого неотрицателен и определяется весовой функцией <tex>w : E \to \mathbb{R}</tex>, алгоритм Дейкстры находит длины кратчайших [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|путей]] из заданной [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|вершины]] <tex>s</tex> до всех остальных.<br>
В алгоритме поддерживается множество вершин <tex>U</tex>, для которых уже вычислены длины кратчайших путей до них из <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \notin U</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>U</tex> и производится релаксация всех исходящих из неё рёбер.
== Псевдокод ==
'''func''' dijkstra(s)''':''' '''for''' i = 0 '''to''' n <codefont color="green">Для всех// n {{---}} количество вершин в графе</codefont> d[v] = <tex>u \in Vinfty</tex>: <tex>d used[uv] \gets \infty</tex>= ''false''<tex> d[s] \gets = 0 '''for''' i = 0\</tex><br>'''to''' n v = ''null'' '''for''' j = 0 '''to''' n <texfont color="green"> U \gets \emptyset// найдем вершину с минимальным расстоянием</tex><brfont> '''if''' !used[j] '''and''' (v == ''null'' '''or''' d[j] <code>Пока</code> <tex>\exists d[v \notin U</tex>]): <code>Пусть</code> <tex> v \notin U : = j '''if''' d[v]== </tex> <code> минимальный \infty</codetex> '''break''' used[v] = ''true'' '''for''' e : исходящие из ''v'' рёбра <codefont color="green">Для всех</code> <tex>u \notin U</tex> <code>такихпроизведём релаксацию по всем рёбрам, что</code> <tex>vu \in Eисходящим из ''v''</texfont>:: <code>если</code> <tex> '''if''' d[uv] > + e.len < d[ve.to] + w(vu)</tex> <code>то</code>::: <tex> d[ue.to] \gets = d[v] + w (vu)</tex>: <tex>U \gets v </tex>e.len
== Обоснование корректности ==
