Алгоритм Дейкстры не работает с рёбрами, имеющими отрицательный вес. 310 Это связано с тем, что алгоритм предполагает, что добавление новых рёбер всегда увеличивает длину пути. 3 При наличии отрицательных весов алгоритм может зациклиться или выдать неверный результат. 4

Некоторые недостатки алгоритма Дейкстры:

• Неэффективен для больших графов. 8 Стандартная реализация алгоритма работает со сложностью O(n²), где n — количество вершин. 4 Для графа с миллионом вершин это примерно триллион операций. 4
• Не приспособлен для работы с динамически изменяющимися графами. 8 Если в процессе работы алгоритма веса рёбер меняются, Дейкстра не сможет автоматически адаптироваться. 4
• Требует значительных ресурсов памяти. 4 Для больших графов алгоритму нужно много памяти для хранения информации о расстояниях, посещённых вершинах и предшественниках. 4

Алгоритм Беллмана-Форда, в отличие от Дейкстры, способен работать с графами, имеющими рёбра с отрицательными весами. 38

Некоторые преимущества алгоритма Беллмана-Форда:

• Позволяет обрабатывать отрицательные веса. 3
• Способен обнаруживать циклы отрицательного веса (циклы в графе, сумма весов рёбер которых отрицательна). 3
• Подходит для решения задач, в которых требуется найти кратчайший путь во взвешенном графе, содержащем рёбра с отрицательным весом. 3

Некоторые недостатки алгоритма Беллмана-Форда:

• Для графов с большим числом рёбер этот алгоритм может работать медленнее, чем Дейкстра. 8