Алгоритм Дейкстры. Почему все веса должны быть больше, либо равны нулю?

Сидел, читал про алгоритм Дейкстры и Форда-Беллмана. В определении данных алгоритмов есть условие - всё веса рёбер должны быть больше, либо равны нулю. Объяснения не нашел. Почему накладывается такое условие?

Ответ

На самом деле все по-другому.
Алгоритм Дейкстры является в некотором роде "жадным" - найдя один раз минимальный путь до вершины, он фиксирует его как минимальный навсегда - поскольку путь через другие вершины не может быть короче найденного.
Но в графе с отрицательными дугами это не так! Рассмотрим такой вот граф, заданный матрицей смежности:
+---+---+---+---+ | | А | Б | В | +---+---+---+---+ | А | | 4 | 2 | +---+---+---+---+ | Б | | |-3 | +---+---+---+---+ | В | | | | +---+---+---+---+
Запустим алгоритм Дейкстры из вершины А. На первом шаге у нас будут расстояния до вершин Б и В - 4 и 2 соответственно, поэтому алгоритм решит, что уже нашел кратчайший путь к вершине В - ведь кратчайший путь к В никак не может идти через Б, не так ли? С сожалению, не так - очевидно, путь А-Б-В на самом деле короче чем А-В
Поэтому алгоритм Дейкстры не может работать при наличии в графе отрицательных дуг.
Алгоритм же Форда-Беллмана (он же алгоритм Беллмана-Форда) таких предположений не делает - а потому может работать почти на любых графах, ценой значительного замедления по сравнению с Дейкстрой. Почему я говорю "почти на любых"? Потому что алгоритм Форда-Беллмана все равно не может работать на графах с отрицательными циклами.
Просто потому что понятие "кратчайший путь" в таких графах не определено. Всегда можно пройтись по отрицательному циклу еще один раз - и получить еще более короткий путь.
Тем не менее, существует модификация алгоритма Беллмана-Форда, которая позволяет обнаружить цикл отрицательного веса в графе. Достаточно ограничить количество итераций количеством вершин в графе - после чего сделать еще одну итерацию. До вершин, веса которых обновились на последней итерации, не существует кратчайшего пути из-за цикла.
Ну и последнее. Если рассматривать неориентированный граф - то надо помнить, что в нем любое ребро отрицательного веса автоматически создает цикл отрицательного веса из двух вершин.