В чем отличие алгоритмов Дейкстры и Беллмана-Форда при работе с отрицательными весами?

Основное отличие алгоритмов Дейкстры и Беллмана-Форда при работе с отрицательными весами заключается в том, что первый не работает с такими весами, а второй может их обрабатывать. infostart.ru tproger.ru

Алгоритм Дейкстры предполагает, что добавление новых рёбер всегда увеличивает длину пути. infostart.ru При наличии отрицательных весов алгоритм может зациклиться или выдать неверный результат, так как он основан на предположении, что, пройдя по ребру, нельзя уменьшить общее расстояние. kurshub.ru

Алгоритм Беллмана-Форда, в отличие от Дейкстры, способен работать с графами, имеющими рёбра с отрицательными весами. tproger.ru Более того, он позволяет определить, есть ли в графе цикл отрицательного веса (цикл, сумма весов рёбер которого отрицательна). infostart.ru Наличие такого цикла означает, что не существует кратчайшего пути, так как можно бесконечно «наматывать» круги по этому циклу, каждый раз уменьшая длину пути. infostart.ru

Пользователь

Время добавления