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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Задача
 
{{Задача
 
|definition=Для заданного взвешенного графа <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. Веса всех рёбер неотрицательны.
 
|definition=Для заданного взвешенного графа <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. Веса всех рёбер неотрицательны.

Текущая версия на 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].

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