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

Эта статья находится в разработке!

В ориентированном взвешанном графе [math]G = (V, E)[/math], вес рёбер которого неотрицателен и определяется весовой функцией [math]w(uv) \geqslant 0[/math], Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины [math]s[/math] до всех остальных.

Алгоритм

В алгоритме поддерживается множество вершин [math]S[/math], для которых уже вычислены кратчайшие пути к ним из вершины [math]s[/math]. На каждой итерации основного цикла выбирается вершина [math] u \in V \setminus S[/math], которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина [math]u[/math] добавляется в множество [math]S[/math] и производится релаксация всех исходящих из неё рёбер.

Псевдокод

Dijkstra([math]G[/math], [math]w[/math], [math]s[/math])
  [math]d \gets \infty[/math]
  [math]d[s] \gets 0[/math]
  [math]S \gets \emptyset[/math]
  while [math]V \setminus S \neq \emptyset[/math]
      do argmin([math]v : v \in V \setminus S, d[v][/math])
         [math]S \gets S \cup \{u\}[/math]
         for [math](uv) \in E[/math]
             do relax([math]u[/math], [math]v[/math], [math]w[/math])

Обоснование корректности работы

Теорема:

После окончания работы алгоритма Дейкстры для всех вершин будет выполняться равенство

Доказательство:

Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин [math]v \in S[/math] выполняется [math]d[v] = \delta(s, u)[/math]

Инициализация. Изначально множество [math]S[/math] пусто, инвариант выполняется.

Сохранение.

Оценка сложности

Литература

Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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