Какие алгоритмы поиска пути в графах существуют?

Что проверяют

Знаете ли вы, какой алгоритм брать под конкретный граф: есть ли веса, бывают ли они отрицательными, нужен путь из одной вершины или между всеми парами. Следом часто просят написать Дейкстру на heapq или BFS с восстановлением пути через словарь родителей.

Как отвечать

Стройте ответ от свойств графа, а не списком названий:

• BFS: невзвешенный граф, кратчайший путь по числу рёбер, O(V + E). Очередь в Python это collections.deque;
• DFS: достижимость, компоненты связности, поиск циклов, топологическая сортировка. Кратчайший путь не гарантирует. Рекурсивная версия упирается в лимит рекурсии (по умолчанию 1000, sys.getrecursionlimit()), поэтому на больших графах её пишут итеративно;
• Дейкстра: неотрицательные веса, путь от одной вершины до всех. С бинарной кучей O((V + E) log V). В heapq нет операции уменьшения ключа, поэтому в кучу кладут дубликаты, а устаревшие записи пропускают при извлечении;
• A-star: Дейкстра плюс эвристика оценки оставшегося пути. Если эвристика допустима, то есть не переоценивает расстояние, найденный путь оптимален. На сетке берут манхэттенское или евклидово расстояние;
• Беллман-Форд: работает с отрицательными весами за O(V·E) и обнаруживает отрицательный цикл;
• Флойд-Уоршелл: все пары вершин за O(V³), разумен для графов на сотни вершин;
• 0-1 BFS: веса только 0 и 1, двусторонняя очередь, линейное время.

Для рабочих задач назовите готовое: в networkx есть shortest_path, dijkstra_path, astar_path, bellman_ford_path, а для больших разреженных графов быстрее scipy.sparse.csgraph.

Где спотыкаются

Применяют Дейкстру к графу с отрицательными весами. Алгоритм не падает, а молча возвращает неверный ответ. Здесь нужен Беллман-Форд или перевзвешивание по Джонсону.

Пишут BFS через list.pop(0). Каждое извлечение стоит O(n), и линейный алгоритм превращается в квадратичный.

Говорят, что A-star всегда быстрее Дейкстры. С нулевой эвристикой он и есть Дейкстра, а с переоценивающей теряет гарантию оптимального пути.