Сравнение с Bellman-Ford

Дейкстра: требует неотрицательные веса (иначе неправильный результат), O((V+E) log V), жадный алгоритм (выбираем ближайшую вершину). Bellman-Ford: работает с отрицательными весами, детектирует отрицательные циклы, O(VE) — медленнее. Почему Дейкстра не работает с отрицательными: пометив вершину как обработанную, позже может найтись более короткий путь через отрицательное ребро. Пример: s→a (1), s→b (4), a→b (-3) → Дейкстра найдёт s→b = 4, пропустив s→a→b = -2. Применение: Bellman-Ford для графов с отрицательными весами (arbitrage detection)