Поиск кратчайших путей на графах: Алгоритмы Дейкстры и Беллмана-Форда
Когда вы открываете навигатор на смартфоне и просите проложить маршрут от дома до работы в обход пробок, в недрах приложения запускаются алгоритмы дискретной математики по поиску кратчайших путей на взвешенных графах. В отличие от простого поиска в ширину (BFS), который эффективен только для сетей с одинаковой длиной ребер, реальный мир требует работы с графами, где каждое ребро имеет свой "вес" — время, километраж или стоимость проезда.
Королем алгоритмов на взвешенных графах является Алгоритм Дейкстры, предложенный нидерландским ученым Эдсгером Дейкстрой в 1959 году. Алгоритм находит кратчайшие пути от одной стартовой вершины до всех остальных. Он относится к классу жадных алгоритмов.
Логика работы алгоритма Дейкстры элегантна:
- Каждой вершине присваивается метка "расстояние от старта". Для старта это 0, для остальных — бесконечность.
- Все вершины помещаются в очередь с приоритетом, где приоритетом служит текущее известное расстояние до них.
- Алгоритм извлекает из очереди вершину с наименьшим расстоянием (в начале это стартовая вершина).
- Для каждого соседа извлеченной вершины алгоритм проверяет: если текущее расстояние до нее плюс вес ребра до соседа меньше, чем записанное в соседе расстояние, то метка соседа обновляется (происходит релаксация ребра).
- Процесс повторяется, пока очередь не опустеет.
Однако у алгоритма Дейкстры есть фундаментальное математическое ограничение (ахиллесова пята): он выдает неверные результаты, если в графе есть ребра с отрицательным весом. Жадная природа заставляет его "финализировать" расстояние до вершины, как только она извлекается из приоритетной очереди, не предполагая, что в будущем более длинный маршрут вдруг может "окупиться" отрицательным участком.
Чтобы решить эту проблему, применяется более медленный, но универсальный Алгоритм Беллмана-Форда. Он основан на принципах динамического программирования. Вместо жадного выбора, алгоритм Беллмана-Форда просто выполняет релаксацию абсолютно всех ребер графа (V-1) раз, где V — количество вершин. Если на V-той итерации все еще возможно улучшить какой-то путь, алгоритм радостно (или печально) сообщает, что в графе присутствует цикл с отрицательным весом, и понятие "кратчайшего пути" теряет математический смысл, так как по такому циклу можно кружить бесконечно, уменьшая общую стоимость пути до минус бесконечности.
Эти алгоритмы — не просто теория. Алгоритм Дейкстры (в его модификации SPF) является "движком" протокола маршрутизации OSPF в интернете, а алгоритм Беллмана-Форда лежит в основе работы дистанционно-векторного протокола RIP.
