Коротко, с доказательствами и сравнениями.
Dijkstra
- Постановка: на взвешенном ориентированном/неориентированном графе с весами рёбер $w(e)\ge 0$ ищет кратчайшие расстояния от истока $s$ до всех вершин.
- Сложность (зависит от структуры очереди при извлечении минимума):
- простой массив: $O(V^2)$.
- двоичная куча (binary heap): $O((V+E)\log V)=O(E\log V)$.
- Фибоначчиева куча: $O(E+V\log V)$.
- Идея корректности (инвариант и индукция): поддерживаем множество уже окончательно найденных вершин $S$. При извлечении вершины $u$ с минимальным текущим расстоянием $d[u]$ выполняется инвариант: для любой вершины $x\in S$ $d[x]$ равно длине кратчайшего пути $s\to x$. Доказательство по индукции: база — $s$ с $d[s]=0$. Предположим инвариант верен для всех вершин в $S$. При следующем извлечении $u$ предположим противное — существует путь $P$ от $s$ до $u$ короче $d[u]$. Рассмотрим первую вершину $v$ на $P$, не принадлежащую $S$; её предшественник $p$ принадлежит $S$. По индукции $d[p]$ — истинная кратчайшая длина до $p$, и при релаксации ребра $(p,v)$ должно было установиться $d[v]\le d[p]+w(p,v)$, то есть стоимость до $v$ не больше стоимости префикса $P$, что даёт $d[v]<d[u]$. Тогда куча должна была вытащить $v$ раньше $u$, противоречие. Следовательно, извлечённое $d[u]$ — оптимально.
- Требование: $w(e)\ge 0$ обязательно; при отрицательных рёбрах нужен Беллман–Форд.
A* (A-star)
- Постановка: целевая (goal-directed) версия поиска пути; вместо глобального минимума по $g$ (стоимости от $s$) используется приоритет по $f(n)=g(n)+h(n)$, где $h(n)$ — эвристическая оценка оставшейся стоимости до цели.
- Условия оптимальности:
- admissible (допустимая): $\forall nh(n)\le h^{\ast }(n)$, где $h^{\ast }(n)$ — истинная стоимость от $n$ до цели. Тогда в tree-search A* гарантированно найдёт оптимальный путь.
- consistent (монотонная): $\forall (n,m)h(n)\le c(n,m)+h(m)$. Консистентность ⇒ при графовом поиске вершина, попавшая в закрытое множество (closed), не требует повторного открытия и извлекается с байунтовым окончательным значением.
- Корректность (эскиз доказательства): если эвристика допустима, то никакая вершина на оптимальном пути до цели не имеет $f$-значения больше оптимальной стоимости $C^{\ast }$ — следовательно, A* при извлечении цели с $g(goal)=C^{\ast }$ не мог пропустить более короткий путь. Формально стандартный контрпример/контрпозиция: если A* вернула не оптимальный путь, существует узел на оптимальном пути, имеющий $f$-значение меньше $f$ полученного решения, и он либо был бы извлечён раньше, либо привёл бы к более короткому решению — противоречие.
- Сложность: в худшем случае A* экспандит (рассматривает) все вершины с $f(n)\le C^{\ast }$ (и, возможно, некоторые с $=$), поэтому в худшем случае, при слабой эвристике, поведение эквивалентно Dijkstra и сложность тех же порядков (например, $O(E\log V)$ при двоичной куче). В лучшем случае (идеальная эвристика $h=h^{\ast }$) A* расширяет только вершины на оптимальном пути — число расширенных вершин может быть порядка длины пути.
Сравнение и когда A* полезен / бесполезен
- Когда A* значительно лучше:
- имеется информативная допустимая эвристика $h$ близкая к $h^{\ast }$ (малый остаток), тогда пространство поиска резко сокращается; типичный пример — маршрут на плоскости с эвристикой евклидова/манхэттенова дистанция для положительных геометрических весов.
- граф большой, но цель известна и локализована — A* направляет поиск к цели и не «различивает» весь граф.
- эвристика консистентна ⇒ меньший overhead (нет повторных открытий).
- Когда A* бесполезен или невыгоден:
- слабая эвристика, особенно $h\equiv 0$ — A* сводится к Dijkstra, ускорения нет.
- если нужно кратчайшее расстояние до всех вершин (вместо одного конкретного целевого узла) — Dijkstra естественнее, т.к. A* ориентирован на одиночную цель.
- множество различных целей подряд — лучше предобработки (например, многоисточниковые алгоритмы, алгоритмы с преландмарками) чем многократный A* без инвалидаций.
- если вычисление эвристики дорогое — накладные расходы могут перекрыть выигрыш от сокращения числа расширений.
- если веса могут быть отрицательными — ни Dijkstra, ни стандартный A* не применимы (нужен Bellman–Ford / алгоритмы для графов с отрицателями).
- если эвристика недопустима (overestimate), A* может вернуть не оптимальный путь.
Практические замечания
- Консистентность удобна вплоть до того, что тогда закрытое множество не нуждается в повторном рассмотрении; при недомонотонном $h$ нужен reopening (и корректность сложнее поддерживать).
- Для многократных запросов часто выгодны предобученные/прелендмарки (ALT), которые делают A* «почти мгновенным».
- Выбор структуры данных (куча, хеши) влияет на константы и поведение при плотных/разреженных графах.
Кратко: Dijkstra — гарантированно оптимален и эффективен для поиска всех кратчайших при неотрицательных весах; A* — Dijkstra + эвристика, сохраняет оптимальность при допустимой $h$ и может резко сократить поисковое пространство, но только если эвристика информативна и недорогая; при слабой или отсутствующей эвристике A* по сути бесполезен и сводится к Dijkstra.