Алгоритм Дейкстры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлено доказательство и оценка времени работы)
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 9 участников)
Строка 1: Строка 1:
{{В разработке}}
+
{{Задача
 
+
|definition=Для заданного взвешенного графа <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. Веса всех рёбер неотрицательны.
В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.
+
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка  кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.
+
В [[Ориентированный граф|ориентированном]] взвешенном [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] <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> и производится релаксация всех исходящих из неё рёбер.
  
 
== Псевдокод ==
 
== Псевдокод ==
  '''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
+
  '''func''' dijkstra(s)''':'''
  <tex>d \gets \infty</tex>
+
    '''for''' <tex>v \in V</tex>                  
  <tex>d[s] \gets 0</tex>
+
        d[v] = <tex>\infty</tex>
  <tex>S \gets \emptyset</tex>
+
        used[v] = ''false''
  '''while''' <tex>V \setminus S \neq \emptyset</tex>
+
    d[s] = 0
      '''do''' ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
+
    '''for''' <tex>i \in V</tex>
          <tex>S \gets S \cup \{u\}</tex>
+
        v = ''null''
          '''for''' <tex>(uv) \in E</tex>
+
        '''for''' <tex>j \in V</tex>                        <font color="green">// найдём вершину с минимальным расстоянием</font>
              '''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)
+
            '''if''' !used[j] '''and''' (v == ''null'' '''or''' d[j] < d[v])
 +
                v = j
 +
        '''if''' d[v] == <tex>\infty</tex>
 +
            '''break'''
 +
        used[v] = ''true''
 +
        '''for''' e : исходящие из ''v'' рёбра    <font color="green">// произведём релаксацию по всем рёбрам, исходящим из ''v''</font>
 +
            '''if''' d[v] + e.len < d[e.to]
 +
                d[e.to] = d[v] + e.len
  
== Обоснование корректности работы ==
+
== Обоснование корректности ==
 
{{Теорема
 
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
+
|statement=
 +
Пусть <tex>G = (V, E)</tex> {{---}} ориентированный взвешенный граф, вес рёбер которого неотрицателен, <tex>s</tex> {{---}} стартовая вершина.
 +
Тогда после выполнения алгоритма Дейкстры <tex>d(u) = \rho(s, u)</tex> для всех <tex>u</tex>, где <tex>\rho(s, u)</tex> {{---}} длина кратчайшего пути из вершины <tex>s</tex> в вершину <tex>u</tex>
 
|proof=
 
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>
+
Докажем по индукции, что в момент посещения любой вершины <tex>u</tex>, <tex>d(u) = \rho(s, u)</tex>.
 
+
* На первом шаге выбирается <tex>s</tex>, для неё выполнено: <tex>d(s) = \rho(s, s) = 0</tex>
'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.
+
* Пусть для <tex>n</tex> первых шагов алгоритм сработал верно и на <tex>n + 1</tex> шагу выбрана вершина <tex>u</tex>. Докажем, что в этот момент <tex>d(u) = \rho(s, u)</tex>. Для начала отметим, что для любой вершины <tex>v</tex>, всегда выполняется <tex>d(v) \geqslant \rho(s, v)</tex> (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть <tex>P</tex> — кратчайший путь из <tex>s</tex> в <tex>u</tex>, <tex>v</tex> {{---}} первая непосещённая вершина на <tex>P</tex>, <tex>z</tex> {{---}} предшествующая ей (следовательно, посещённая). Поскольку путь <tex>P</tex> кратчайший, его часть, ведущая из <tex>s</tex> через <tex>z</tex> в <tex>v</tex>, тоже кратчайшая, следовательно <tex>\rho(s, v) = \rho(s, z) + w(zv)</tex>. По предположению индукции, в момент посещения вершины <tex>z</tex> выполнялось <tex>d(z) = \rho(s, z)</tex>, следовательно, вершина <tex>v</tex> тогда получила метку не больше чем <tex>d(z) + w(zv) = \rho(s, z) + w(zv) = \rho(s, v)</tex>, следовательно, <tex>d(v) = \rho(s, v)</tex>. С другой стороны, поскольку сейчас мы выбрали вершину <tex>u</tex>, её метка минимальна среди непосещённых, то есть <tex>d(u) \leqslant d(v) = \rho(s, v) \leqslant \rho(s, u)</tex>, где второе неравенсто верно из-за ранее упомянутого определения вершины <tex>v</tex> в качестве первой непосещённой вершины на <tex>P</tex>, то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с <tex>d(u) \geqslant \rho(s, u)</tex>, имеем <tex>d(u) = \rho(s, u)</tex>, что и требовалось доказать.
 
 
[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
 
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.
 
  
Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.
+
*Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент <tex>d(u) = \rho(s, u)</tex> для всех <tex>u</tex>.
 
 
Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.
 
 
 
Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.
 
 
 
'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
 
 
}}
 
}}
  
 
== Оценка сложности ==
 
== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', ассимптотика её работы зависит от реализации.
+
В реализации алгоритма присутствует функция выбора вершины с минимальным значением <tex>d</tex> и релаксация по всем рёбрам для данной вершины. Асимптотика работы зависит от реализации.
  
Таким образом:
+
Пусть <tex>n</tex> {{---}} количество вершин в графе, <tex>m</tex> {{---}} количество рёбер в графе.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
+
 
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
+
{| class="wikitable"
!style="background:#f2f2f2"|Ассимптотика времени работы
 
 
|-
 
|-
|style="background:#f9f9f9"|Наивная реализация
+
! rowspan="2" |
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
+
! colspan="3" | Время работы
 +
! rowspan="2" | Описание
 
|-
 
|-
|style="background:#f9f9f9"|Куча
+
! Поиск минимума
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
+
! Релаксация
 +
! Общее
 
|-
 
|-
|style="background:#f9f9f9"|Куча Фибоначчи
+
| align="center" | Наивная реализация
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
+
| align="center" | <tex>O(n)</tex>
 +
| align="center" | <tex>O(1)</tex>
 +
| align="center" | <tex>O(n^2 + m)</tex>
 +
| align="center" | <tex>n</tex> раз осуществляем поиск вершины с минимальной величиной <tex>d</tex> среди <tex>O(n)</tex> непомеченных вершин и <tex>m</tex> раз проводим релаксацию за <tex>O(1)</tex>. Для плотных графов (<tex>m \approx n^2</tex>) данная асимптотика является оптимальной.
 +
|-
 +
| align="center" | [[Двоичная куча]]
 +
| align="center" | <tex>O(\log{n})</tex>
 +
| align="center" | <tex>O(\log{n})</tex>
 +
| align="center" | <tex>O(m\log{n})</tex>
 +
| align="center" | Используя двоичную кучу можно выполнять операции извлечения минимума и обновления элемента за <tex>O(\log{n})</tex>. Тогда время работы алгоритма Дейкстры составит <tex>O(n\log{n} + m\log{n}) = O(m\log{n})</tex>.
 +
|-
 +
| align="center" | [[Фибоначчиевы кучи|Фибоначчиева куча]]
 +
| align="center" | <tex>O(\log{n})</tex>
 +
| align="center" | <tex>O(1)</tex>
 +
| align="center" | <tex>O(n\log{n} + m)</tex>
 +
| align="center" | Используя Фибоначчиевы кучи можно выполнять операции извлечения минимума за <tex>O(\log{n})</tex> и обновления элемента за <tex>O(1)</tex>. Таким образом, время работы алгоритма составит <tex>O(n\log{n} + m)</tex>.
 
|}
 
|}
  
 +
На практике удобно использовать стандартные контейнеры (например, '''std::set''' или '''std::priority_queue''' в C++). <br>При реализации необходимо хранить вершины, которые упорядочены по величине <tex>d</tex>, для этого в контейнер можно помещать пару {{---}} расстояние-вершина. В результате будут храниться пары, упорядоченные по расстоянию.
 +
 +
Изначально поместим в контейнер стартовую вершину <tex>s</tex>. Основной цикл будет выполняться, пока в контейнере есть хотя бы одна вершина. На каждой итерации извлекается вершина с наименьшим расстоянием <tex>d</tex> и выполняются релаксации по рёбрам из неё. При выполнении успешной релаксации нужно удалить из контейнера вершину, до которой обновляем расстояние, а затем добавить её же, но с новым расстоянием.
 +
<br>В обычных кучах нет операции удаления произвольного элемента. При релаксации можно не удалять старые пары, в результате чего в куче может находиться одновременно несколько пар расстояние-вершина для одной вершины (с разными расстояниями). Для корректной работы при извлечении из кучи будем проверять расстояние: пары, в которых расстояние отлично от <tex>d[v]</tex> будем игнорировать. При этом асимптотика будет <tex>O(m\log{m})</tex> вместо <tex>O(m\log{n})</tex>.
  
== Литература ==
+
== Источники информации ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
+
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
 +
* [http://e-maxx.ru/algo/dijkstra MAXimal :: algo :: Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры]
 +
* [https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры Википедия — Алгоритм Дейкстры]
 +
* [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Wikipedia — Dijkstra's algorithm]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Текущая версия на 19:30, 4 сентября 2022

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


Алгоритм

В ориентированном взвешенном графе [math]G = (V, E)[/math], вес рёбер которого неотрицателен и определяется весовой функцией [math]w : E \to \mathbb{R}[/math], алгоритм Дейкстры находит длины кратчайших путей из заданной вершины [math]s[/math] до всех остальных.
В алгоритме поддерживается множество вершин [math]U[/math], для которых уже вычислены длины кратчайших путей до них из [math]s[/math]. На каждой итерации основного цикла выбирается вершина [math] u \notin U[/math], которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина [math]u[/math] добавляется в множество [math]U[/math] и производится релаксация всех исходящих из неё рёбер.

Псевдокод

func dijkstra(s):
    for [math]v \in V[/math]                    
        d[v] = [math]\infty[/math]
        used[v] = false
    d[s] = 0
    for [math]i \in V[/math]
        v = null
        for [math]j \in V[/math]                        // найдём вершину с минимальным расстоянием
            if !used[j] and (v == null or d[j] < d[v])
                v = j
        if d[v] == [math]\infty[/math]
            break
        used[v] = true
        for e : исходящие из v рёбра     // произведём релаксацию по всем рёбрам, исходящим из v
            if d[v] + e.len < d[e.to]
                d[e.to] = d[v] + e.len

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

Теорема:
Пусть [math]G = (V, E)[/math] — ориентированный взвешенный граф, вес рёбер которого неотрицателен, [math]s[/math] — стартовая вершина. Тогда после выполнения алгоритма Дейкстры [math]d(u) = \rho(s, u)[/math] для всех [math]u[/math], где [math]\rho(s, u)[/math] — длина кратчайшего пути из вершины [math]s[/math] в вершину [math]u[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции, что в момент посещения любой вершины [math]u[/math], [math]d(u) = \rho(s, u)[/math].

  • На первом шаге выбирается [math]s[/math], для неё выполнено: [math]d(s) = \rho(s, s) = 0[/math]
  • Пусть для [math]n[/math] первых шагов алгоритм сработал верно и на [math]n + 1[/math] шагу выбрана вершина [math]u[/math]. Докажем, что в этот момент [math]d(u) = \rho(s, u)[/math]. Для начала отметим, что для любой вершины [math]v[/math], всегда выполняется [math]d(v) \geqslant \rho(s, v)[/math] (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть [math]P[/math] — кратчайший путь из [math]s[/math] в [math]u[/math], [math]v[/math] — первая непосещённая вершина на [math]P[/math], [math]z[/math] — предшествующая ей (следовательно, посещённая). Поскольку путь [math]P[/math] кратчайший, его часть, ведущая из [math]s[/math] через [math]z[/math] в [math]v[/math], тоже кратчайшая, следовательно [math]\rho(s, v) = \rho(s, z) + w(zv)[/math]. По предположению индукции, в момент посещения вершины [math]z[/math] выполнялось [math]d(z) = \rho(s, z)[/math], следовательно, вершина [math]v[/math] тогда получила метку не больше чем [math]d(z) + w(zv) = \rho(s, z) + w(zv) = \rho(s, v)[/math], следовательно, [math]d(v) = \rho(s, v)[/math]. С другой стороны, поскольку сейчас мы выбрали вершину [math]u[/math], её метка минимальна среди непосещённых, то есть [math]d(u) \leqslant d(v) = \rho(s, v) \leqslant \rho(s, u)[/math], где второе неравенсто верно из-за ранее упомянутого определения вершины [math]v[/math] в качестве первой непосещённой вершины на [math]P[/math], то есть вес пути до промежуточной вершины не превосходит веса пути до конечной вершины вследствие неотрицательности весовой функции. Комбинируя это с [math]d(u) \geqslant \rho(s, u)[/math], имеем [math]d(u) = \rho(s, u)[/math], что и требовалось доказать.
  • Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент [math]d(u) = \rho(s, u)[/math] для всех [math]u[/math].
[math]\triangleleft[/math]

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

В реализации алгоритма присутствует функция выбора вершины с минимальным значением [math]d[/math] и релаксация по всем рёбрам для данной вершины. Асимптотика работы зависит от реализации.

Пусть [math]n[/math] — количество вершин в графе, [math]m[/math] — количество рёбер в графе.

Время работы Описание
Поиск минимума Релаксация Общее
Наивная реализация [math]O(n)[/math] [math]O(1)[/math] [math]O(n^2 + m)[/math] [math]n[/math] раз осуществляем поиск вершины с минимальной величиной [math]d[/math] среди [math]O(n)[/math] непомеченных вершин и [math]m[/math] раз проводим релаксацию за [math]O(1)[/math]. Для плотных графов ([math]m \approx n^2[/math]) данная асимптотика является оптимальной.
Двоичная куча [math]O(\log{n})[/math] [math]O(\log{n})[/math] [math]O(m\log{n})[/math] Используя двоичную кучу можно выполнять операции извлечения минимума и обновления элемента за [math]O(\log{n})[/math]. Тогда время работы алгоритма Дейкстры составит [math]O(n\log{n} + m\log{n}) = O(m\log{n})[/math].
Фибоначчиева куча [math]O(\log{n})[/math] [math]O(1)[/math] [math]O(n\log{n} + m)[/math] Используя Фибоначчиевы кучи можно выполнять операции извлечения минимума за [math]O(\log{n})[/math] и обновления элемента за [math]O(1)[/math]. Таким образом, время работы алгоритма составит [math]O(n\log{n} + m)[/math].

На практике удобно использовать стандартные контейнеры (например, std::set или std::priority_queue в C++).
При реализации необходимо хранить вершины, которые упорядочены по величине [math]d[/math], для этого в контейнер можно помещать пару — расстояние-вершина. В результате будут храниться пары, упорядоченные по расстоянию.

Изначально поместим в контейнер стартовую вершину [math]s[/math]. Основной цикл будет выполняться, пока в контейнере есть хотя бы одна вершина. На каждой итерации извлекается вершина с наименьшим расстоянием [math]d[/math] и выполняются релаксации по рёбрам из неё. При выполнении успешной релаксации нужно удалить из контейнера вершину, до которой обновляем расстояние, а затем добавить её же, но с новым расстоянием.
В обычных кучах нет операции удаления произвольного элемента. При релаксации можно не удалять старые пары, в результате чего в куче может находиться одновременно несколько пар расстояние-вершина для одной вершины (с разными расстояниями). Для корректной работы при извлечении из кучи будем проверять расстояние: пары, в которых расстояние отлично от [math]d[v][/math] будем игнорировать. При этом асимптотика будет [math]O(m\log{m})[/math] вместо [math]O(m\log{n})[/math].

Источники информации