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

Алгоритм Дейкстры ( / ˈd aɪ k s t r ə z / DYKE -strəz ) — алгоритм поиска кратчайших путей между узлами в графе , который может представлять, например, дорожные сети . Он был задуман ученым-компьютерщиком Эдсгером В. Дейкстрой в 1956 году и опубликован тремя годами позже. ^{[4] [5] [6]}

Алгоритм существует во многих вариантах. Оригинальный алгоритм Дейкстры нашел кратчайший путь между двумя заданными узлами ^[6] , но более распространенный вариант фиксирует один узел как «исходный» узел и находит кратчайшие пути от источника ко всем другим узлам в графе, создавая кратчайший путь . дерево .

Для данного исходного узла в графе алгоритм находит кратчайший путь между этим узлом и всеми остальными. ^{[7] : 196–206} Его также можно использовать для поиска кратчайших путей от одного узла к одному узлу назначения путем остановки алгоритма после определения кратчайшего пути к узлу назначения. Например, если узлы графа представляют города, а стоимость краевого пути представляет собой расстояние между парами городов, соединенных прямой дорогой (для простоты игнорируйте красный свет, знаки остановки, платные дороги и другие препятствия), можно использовать алгоритм Дейкстры. найти кратчайший маршрут между одним городом и всеми другими городами. Широко используемым применением алгоритмов кратчайшего пути являются протоколы сетевой маршрутизации , в первую очередь IS-IS .(от промежуточной системы к промежуточной системе) и сначала открыть кратчайший путь ( OSPF ). Он также используется в качестве подпрограммы в других алгоритмах, таких как алгоритм Джонсона .

Алгоритм Дейкстры использует метки, которые представляют собой положительные целые или действительные числа, которые полностью упорядочены . Его можно обобщить для использования любых частично упорядоченных меток при условии, что последующие метки (последующая метка создается при пересечении ребра) монотонно неубывают. Это обобщение называется общим алгоритмом поиска кратчайшего пути Дейкстры. ^[8]

Алгоритм Дейкстры использует структуру данных для хранения и запроса частичных решений, отсортированных по расстоянию от начала. Хотя исходный алгоритм использует очередь с минимальным приоритетом и работает во времени (где — количество узлов, а — количество ребер), его также можно реализовать с использованием массива. Идея этого алгоритма также дана в Leyzorek et al. 1957 . Fredman & Tarjan 1984 предлагают использовать очередь с минимальным приоритетом кучи Фибоначчи , чтобы оптимизировать сложность времени выполнения до . Это асимптотически самый быстрый из известных алгоритмов поиска кратчайшего пути с одним источником для произвольных ориентированных графов .${\ Displaystyle \ Theta ({| V | + | E |) \ журнал | V |)}$${\ Displaystyle | В |}$${\ Displaystyle | Е |}$${\ Displaystyle \ Тета (| В | ^ {2})}$${\ Displaystyle \ Тета (| Е | + | В | \ журнал | В |)}$с неограниченными неотрицательными весами. Однако специальные случаи (например, ограниченные/целочисленные веса, ориентированные ациклические графы и т. д.) действительно можно улучшить, как подробно описано в разделе Специализированные варианты . Кроме того, если разрешена предварительная обработка, такие алгоритмы, как иерархия сжатия , могут быть на семь порядков быстрее.

Иллюстрация алгоритма Дейкстры, находящего путь от начального узла (внизу слева, красный) к целевому узлу (вверху справа, зеленый) в задаче планирования движения робота . Открытые узлы представляют собой «предварительный» набор (также известный как набор «непосещенных» узлов). Заполненные узлы — это посещенные узлы, цвет которых соответствует расстоянию: чем зеленее, тем ближе. Узлы во всех различных направлениях исследуются единообразно, появляясь более или менее в виде кругового волнового фронта , поскольку алгоритм Дейкстры использует эвристику , тождественно равную 0.

Демонстрация алгоритма Дейкстры, основанного на евклидовом расстоянии. Красные линии — это кратчайшие пути, т. е. соединяющие u и prev[ u ]. Синие линии показывают, где происходит расслабление, т. е. соединение v с узлом u в Q , что дает более короткий путь от источника к v .