Алгоритмы

Dijkstra: Кратчайший путь во взвешенном графе

Цели урока

  • Понять, почему BFS не работает для взвешенных графов
  • Реализовать Dijkstra с priority queue
  • Знать сложность разных реализаций
  • Понимать ограничение на отрицательные веса

Предварительные знания

  • BFS
  • Куча (Heap)
  • BFS: Поиск в ширину

Как Google Maps находит маршрут за миллисекунды среди миллиардов возможных путей? Алгоритм Дейкстры (1956) - жадный подход, который гарантированно находит оптимум.

  • GPS-навигация
  • Маршрутизация сетевых пакетов (OSPF)
  • Кратчайшие пути в играх
  • Оптимизация логистики

Дейкстра, кофе и двадцать минут размышлений

Алгоритм придумал Эдсгер Дейкстра в 1956 году, и история его рождения стала легендой. По собственному рассказу Дейкстры, он сидел с невестой в кафе в Амстердаме, отдыхая от покупок, и за двадцать минут без бумаги и карандаша придумал кратчайший путь. Задача была прикладной: показать возможности нового компьютера ARMAC, для чего требовался понятный пример, и Дейкстра выбрал кратчайший маршрут между городами Нидерландов. Опубликовал он алгоритм только в 1959 году в короткой статье A Note on Two Problems in Connexion with Graphs в журнале Numerische Mathematik, всего на трёх страницах. В той же заметке был и второй алгоритм, для минимального остовного дерева. Дейкстра позже говорил, что отсутствие карандаша было плюсом: оно заставило избегать лишней сложности. Изначально алгоритм работал за O(V^2). Ускорение пришло позже: Фредман и Тарьян в 1984 году применили фибоначчиеву кучу и довели сложность до O(E + V log V), что до сих пор остаётся асимптотически лучшей границей для плотных графов.

Идея: жадно выбираем ближайшего

**BFS не работает для взвешенных графов.** Путь с меньшим числом рёбер может быть длиннее по весу.

**Идея Дейкстры:** расширяем «облако» от источника, каждый раз добавляя ближайшую вершину.

**Ограничение:** только для неотрицательных весов! Отрицательные рёбра ломают жадный выбор.

Почему BFS не подходит для взвешенных графов?

Реализация с heap

**С восстановлением пути:**

Зачем нужен `if u in visited: continue`?

Анализ сложности

РеализацияВремяПамять
Наивная (массив)O(V²)O(V)
Binary HeapO((V + E) log V)O(V)
Fibonacci HeapO(V log V + E)O(V)

**Наивная реализация (O(V²)):**

**В Python heapq** - binary heap. Для больших графов используйте его.

Для графа с V=1000, E=500000 (почти полный), какая реализация лучше?

Проблема отрицательных весов

**Dijkstra ломается при отрицательных весах:**

**Решения для отрицательных весов:**

  • **Bellman-Ford:** O(VE), обрабатывает отрицательные, детектит циклы
  • **Johnson's algorithm:** Перевзвешивание + Dijkstra для всех пар
  • **SPFA:** оптимизация Bellman-Ford (часто быстрее на практике)

**Отрицательный цикл** - путь бесконечно короткий. Dijkstra и Bellman-Ford не дадут ответ, но Bellman-Ford хотя бы обнаружит цикл.

Если рёбра отрицательные, но отрицательного цикла нет, Dijkstra всё равно даст правильный ответ, просто чуть медленнее.

Dijkstra ломается на одном отрицательном ребре даже без циклов: зафиксированная вершина может позже стать достижимой по более короткому пути через отрицательное ребро. Нужен Bellman-Ford или SPFA.

Кажется, что 'отрицательность = бесконечность' и единственная опасность - циклы. Но беда в самой жадной фиксации: когда вершина 'закрыта', алгоритм больше не пересматривает её dist, а отрицательное ребро именно это и должно делать.

В GPS-навигации веса (время проезда) всегда положительны. Dijkstra:

Dijkstra - кратчайший путь

  • Жадно выбирает ближайшую непосещённую вершину
  • Требует неотрицательных весов!
  • O((V+E) log V) с binary heap
  • Используйте heapq в Python
  • Для отрицательных весов - Bellman-Ford

Вопросы для размышления

  • Почему жадный выбор работает для неотрицательных весов, но ломается при появлении даже одного отрицательного ребра - какое именно свойство 'ближайшего' разрушается?
  • В каких сценариях граф 1000 вершин и 500 тысяч рёбер выгоднее обрабатывать наивной O(V^2) реализацией без кучи, чем heapq?
  • A* добавляет к Dijkstra эвристику h(n) - как этот же приём можно перенести в задачи поиска вне графов (планирование, AI search)?

Связанные темы

Dijkstra - частный случай более общих алгоритмов.

  • Bellman-Ford — Обрабатывает отрицательные веса
  • A* — Dijkstra + эвристика
  • Floyd-Warshall — Все пары кратчайших путей

Связанные уроки

  • alg-13-dfs — DFS - базовый обход, Dijkstra его расширяет приоритетами
  • alg-15-bellman-ford — Bellman-Ford - альтернатива для отрицательных рёбер
  • alg-37-a-star — A* - Dijkstra с эвристикой, прямое расширение
  • ds-14-heaps-intro — Priority queue на куче - сердце Dijkstra O((V+E)logV)
  • prob-07-expectation — Greedy выбор минимума - аналог E[cost] оптимизации
  • ml-48-rl-intro
Dijkstra: Кратчайший путь во взвешенном графе

0

1

Войти