Теория графов в математическом программировании: задача о кратчайшем пути

Математическая постановка задачи требует нахождения в ориентированном графе пути от стартовой вершины к целевой, для которого сумма весов (стоимостей) ребер минимальна. Эту задачу можно строго сформулировать как модель линейного программирования: целевая функция минимизирует сумму $c_{ij} x_{ij}$, где переменная $x_{ij}$ равна 1, если ребро включено в путь, и 0 в противном случае. Ограничения модели — это уравнения баланса узлов (сумма входящего потока равна сумме исходящего для всех транзитных узлов). Благодаря тому, что матрица инцидентности графа является тотально унимодулярной, симплекс-метод без дополнительных ухищрений выдаст строго целочисленное (0 или 1) решение.

Несмотря на возможность решения через линейное программирование, на практике применяются графовые алгоритмы, работающие на порядки быстрее. Алгоритм Дейкстры — самый известный представитель жадных методов. Используя структуру данных "очередь с приоритетом" (Priority Queue) или Фибоначчиеву кучу, он "раскрывает" граф, последовательно фиксируя кратчайшие расстояния до ближайших вершин. Ограничение алгоритма Дейкстры — он математически корректен только для графов с неотрицательными весами ребер, так как опирается на принцип, что добавление ребра к пути может только увеличить его длину.

Для графов с отрицательными весами ребер применяется алгоритм Беллмана-Форда, базирующийся на парадигме динамического программирования. Он итеративно "ослабляет" (relax) все ребра графа $|V|-1$ раз. Алгоритм Беллмана-Форда имеет колоссальное прикладное значение в финансах: он способен обнаруживать циклы отрицательной стоимости. В контексте рынка обмена валют (где узлы — это валюты, а логарифмы обменных курсов — веса ребер), цикл отрицательного веса математически эквивалентен безрисковой арбитражной сделке. Алгоритмы трейдинга непрерывно ищут такие циклы для мгновенного извлечения прибыли.

Для интеллектуальных систем поиска на картах (где размер графа измеряется миллионами дорожных перекрестков) используется алгоритм A* (А-звезда). Это эвристическое расширение алгоритма Дейкстры, которое добавляет к фактическому пройденному пути оценочную функцию (эвристику) оставшегося расстояния до цели (например, расстояние по прямой на глобусе). Если эвристика допустима (никогда не переоценивает реальное расстояние), A* математически гарантирует нахождение строго кратчайшего пути, исследуя при этом в тысячи раз меньше узлов, чем слепой поиск. Понимание этих алгоритмов является абсолютной необходимостью для современного аналитика в области сетевой оптимизации.

Список литературы:
1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
2. Ахуджа Р.К., Маньянти Т.Л., Орлин Дж.Б. Сетевые потоки: теория, алгоритмы и приложения. — М.: Мир, 1993.
3. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.