Алгоритм Дейкстры
Алгоритм Дейкстры находит кратчайшие расстояния от одной выбранной вершины до всех остальных в взвешенном графе, если веса всех рёбер неотрицательны.
Для каждой вершины хранят текущую оценку расстояния. В начале расстояние до исходной вершины равно \(0\), до остальных — бесконечности. После выбора вершины её расстояние становится окончательным: при неотрицательных весах более короткий путь через ещё не выбранную вершину уже невозможен.
Здесь \(u\) — выбранная вершина, \(v\) — её сосед, а \(w(u,v)\) — вес ребра между ними. Такая операция называется релаксацией: алгоритм проверяет, не станет ли путь через \(u\) короче уже найденного.
Пусть из вершины \(A\) можно попасть в \(B\) за \(4\), в \(C\) — за \(1\), а из \(C\) в \(B\) — за \(2\). Сначала \(d(A)=0\), затем \(d(C)=1\). Через \(C\) расстояние до \(B\) уточняется: \(1+2=3\), поэтому вместо \(4\) записывается \(3\). Кратчайший путь из \(A\) в \(B\): \(A\to C\to B\), его длина равна \(3\).
Алгоритм Дейкстры нельзя применять, если есть отрицательные веса рёбер: выбранное расстояние может позднее уменьшиться. Для графа без весов обычно используют поиск кратчайшего пути в невзвешенном графе с помощью обхода в ширину. Само понятие пути рассматривается на странице «Кратчайший путь».
Какое условие обязательно для применения алгоритма Дейкстры?
Главное
- Алгоритм Дейкстры ищет кратчайшие пути от одной вершины до остальных.
- Он повторяет выбор вершины с минимальным временным расстоянием и релаксацию её рёбер.
- Алгоритм корректен только при неотрицательных весах.