Рассматривая этот алгоритм, я все никак не мог привыкнуть читать его как Дейкстры. Каждый раз в голове крутился образ персонажа из Ведьмака - шпиона Диикстры. При этом на английском языке они пишутся одинаково - Dijkstra. Но забудем об этом и вернемся к нашему алгоритму.
Представьте карту городов, соединённых дорогами. Каждый город можно представить как вершину графа, каждая дорога — как ребро, а расстояние между городами — как вес ребра. Например, рассмотрим такой граф:
A ──1── B
│ │
4 2
│ │
C ──────D
1
Если мы хотим добраться из A в D по кратчайшему пути, то на глаз ответ не всегда очевиден. Именно для решения таких задач и существует алгоритм Дейкстры, который находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер.
Прежде чем углубляться, стоит уточнить ключевые понятия. Граф — это набор точек (вершин), соединённых линиями (рёбрами). Вес ребра — это число, стоящее на ребре и обозначающее стоимость перехода (расстояние, время, цена и т.п.). Взвешенный граф — это граф, где у каждого ребра есть вес. Кратчайший путь — это маршрут с минимальной суммой весов рёбер. Алгоритм Дейкстры относится к классу жадных алгоритмов: на каждом шаге он выбирает локально лучший вариант, то есть вершину с наименьшим известным расстоянием от старта.
Идею алгоритма можно объяснить простыми словами: вы стоите в начальной точке и хотите узнать расстояния до всех остальных городов. Вы постепенно открываете для себя новые города, всегда переходя сначала в тот, до которого сейчас ближе всего. При этом, попадая в новый город, вы проверяете, не стали ли теперь известные пути до его соседей короче. Этот процесс повторяется, пока не будут обработаны все вершины. Иными словами, на каждом шаге мы идём в ближайший ещё не посещённый город и обновляем расстояния до его соседей.
Рассмотрим работу алгоритма на конкретном примере. Пусть дан граф:
A ──1── B
│ ╱ │
4 2 5
│ ╱ │
C ──1── D
Рёбра и их веса:
- A–B: 1
- A–C: 4
- B–C: 2
- B–D: 5
- C–D: 1
Начальная вершина — A. В начальный момент мы знаем расстояние только до самой себя (ноль), а до всех остальных вершин расстояние полагаем бесконечным. Состояние можно описать так:
Расстояния: A=0, B=∞, C=∞, D=∞
Посещены: {}
Очередь: [(0, A)]
Извлекаем из очереди вершину A с расстоянием 0. Рассматриваем её соседей: до B можно добраться за 0+1=1, что меньше бесконечности, поэтому обновляем расстояние до B. До C можно добраться за 0+4=4, обновляем C. После этого состояния становятся такими:
Расстояния: A=0, B=1, C=4, D=∞
Посещены: {A}
Очередь: [(1, B), (4, C)]
Теперь из очереди выбираем вершину с наименьшим расстоянием — это B (расстояние 1). Из B можно пойти к A (но расстояние 1+1=2 больше уже известного 0, поэтому пропускаем), к C (1+2=3, что меньше текущего 4, обновляем C до 3) и к D (1+5=6, обновляем D с бесконечности до 6). После этого:
Расстояния: A=0, B=1, C=3, D=6
Посещены: {A, B}
Очередь: [(3, C), (4, C_old), (6, D)]
Обратите внимание: в очереди теперь есть два элемента для вершины C: (3, C) и (4, C_old). Это старая запись, которая будет проигнорирована позже.
Следующая ближайшая вершина — C с расстоянием 3. Проверяем соседей: до A (3+4=7 > 0), до B (3+2=5 > 1), до D (3+1=4 < 6) — обновляем D до 4. После обновления:
Расстояния: A=0, B=1, C=3, D=4
Посещены: {A, B, C}
Очередь: [(4, D), (4, C_old), (6, D_old)]
Наконец, извлекаем D с расстоянием 4. Её соседи уже посещены или не дают улучшений. Алгоритм завершается. Итоговые расстояния:
- A = 0
- B = 1
- C = 3
- D = 4
Кратчайшие пути из A:
- A → A : 0
- A → B : A → B (вес 1)
- A → C : A → B → C (1 + 2 = 3)
- A → D : A → B → C → D (1 + 2 + 1 = 4)