Алгоритм Дейкстры
Описание
- Википедия
- YouTube - алгоритм Дейкстры
- YouTube - алгоритм Дейкстры или как навигатор определяет оптимальный маршрут
- GitHub
Алгоритм Дейкстры (Dijkstra's algorithm) - алгоритм для нахождения кратчайших путей от одной вершины графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса и широко применяется в программировании, например, в протоколах маршрутизации OSPF и IS-IS.
Принцип работы
Задача
Дан взвешенный ориентированный граф G(V,E) без ребер отрицательного веса. Необходимо найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.
Неформальное решение
Каждой вершине из множества вершин V сопоставим метку (вес) - минимальное известное расстояние от этой вершины до стартовой вершины a.
Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки.
Работа алгоритма завершается, когда все вершины посещены.
Инициализация
Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности (Infinity).
Это отражает то, что расстояния от a до других вершин пока неизвестны.
Все вершины графа помечаются как непосещенные.
Шаг алгоритма
Если все вершины посещены, алгоритм завершается.
В противном случае, из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку.
Рассматриваем все возможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут ребра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещенные, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом.
Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Сложность
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m - количество ребер в графе G.
В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d используется массив, время работы алгоритма составляет O(n^2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству ребер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма - O(n^2+m), но, так как m <= n(n-1), оно составляет O(n^2).
Реализация
Для реализации алгоритма используется такая структура данных, как очередь с приоритетом:
// algorithms/graphs/dijkstra.js
import PriorityQueue from '../../data-structures/priority-queue'
// Функция принимает граф и начальную вершину
export default function dijkstra(graph, startNode) {
// Расстояния
const distances = {}
// Посещенные вершины
const visited = {}
// Предыдущие вершины
const previous = {}
const queue = new PriorityQueue()
// Инициализируем все расстояния бесконечностью, предполагая, что
// сейчас мы можем достичь только начальную вершину
for (const node of graph.getAllNodes()) {
distances[node.getKey()] = Infinity
previous[node.getKey()] = null
}
// Мы находимся в начальной вершине, расстояние до нее равняется 0
distances[startNode.getKey()] = 0
// Добавляем текущую вершину в очередь
queue.add(startNode, 0)
// Перебираем вершины, пока очередь не опустеет
while (!queue.isEmpty()) {
// Извлекаем ближайшую вершину
const current = queue.poll()
// Перебираем непосещенных соседей текущей вершины
current.getNeighbors().forEach((neighbor) => {
// Если вершина еще не была посещена
if (!visited[neighbor.getKey()]) {
// Обновляем расстояние до каждого соседа
const edge = graph.findEdge(current, neighbor)
const existingDistanceToNeighbor = distances[neighbor.getKey()]
const distanceFromNeighborToCurrent =
distances[current.getKey()] + edge.weight
// Если обнаружено более короткое расстояние
if (distanceFromNeighborToCurrent < existingDistanceToNeighbor) {
distances[neighbor.getKey()] = distanceFromNeighborToCurrent
// Обновляем приоритет соседа в очереди, поскольку он может стать ближе
if (queue.hasValue(neighbor)) {
queue.changePriority(neighbor, distanceFromNeighborToCurrent)
}
// Обновляем предыдущую вершину
previous[neighbor.getKey()] = current
}
// Добавляем соседа в очередь для дальнейшего посещения
if (!queue.hasValue(neighbor)) {
queue.add(neighbor, distances[neighbor.getKey()])
}
}
})
// Добавляем текущую вершину в посещенные во избежание повторного посещения
visited[current.getKey()] = current
}
// Возвращаем набор кратчайших расстояний и
// набор кратчайших путей ко всем вершинам графа
return { distances, previous }
}
Тесты
Обратите внимание: наша реализация алгоритма в отдельных случаях будет работать с графами, содержащими ребра отрицательного веса. Однако сильно полагаться на нее в этом случае не стоит.
Запускаем тесты:
npm run test ./algorithms/graphs/__tests__/dijkstra
