Дейкстра или Беллман-Форд — когда что выбирать на олимпиаде?
Запутался, когда брать Дейкстру, а когда Беллмана-Форда. Оба ищут кратчайший путь из одной вершины. Можете дать чёткий критерий выбора по ограничениям задачи?
2 ответа
Критерий простой — по весам рёбер и размеру графа:
| Случай | Алгоритм | Сложность |
|---|---|---|
Все веса >= 0 |
Дейкстра (на куче) | O(E log V) |
| Есть отрицательные рёбра | Беллман-Форд | O(V·E) |
| Нужно ловить отрицательный цикл | Беллман-Форд | O(V·E) |
| Веса только 0/1 | 0-1 BFS | O(V + E) |
| Граф без весов | BFS | O(V + E) |
| Граф — DAG | топосорт + релаксация | O(V + E) |
Главное правило: есть отрицательные рёбра → только Беллман-Форд (или Джонсон для всех пар). Если весов нет вообще или они 0/1 — не нужна Дейкстра, есть линейные методы. Дейкстра — дефолт для неотрицательных весов.
Дополню по практике: Дейкстра асимптотически быстрее, но Беллман-Форд проще написать без ошибок (нет кучи, нет проверки протухших записей). На контесте, если граф мелкий (V·E укладывается в лимит) и веса неотрицательные, иногда быстрее закодить Беллмана-Форда. Но при E порядка 10^5 и больше Беллман-Форд (10^10 операций) — гарантированный TLE, спасает только Дейкстра. SPFA (очередь-оптимизация Беллмана) в среднем быстра, но имеет антитесты с O(V·E) — на олимпиадах ненадёжна.