Комментарии 4
Отрицательные веса встречаются в различных применениях графов. Например, вместо того чтобы увеличивать стоимость пути, мы можем получить выгоду, следуя по определенному пути.
А если найдется цикл из ребер с отрицательными весами, по нему можно покрутиться?
А если найдется цикл из ребер с отрицательными весами, по нему можно покрутиться?
В этом случае алгоритм Форда-Беллмана не работает. В этом случае вообще сама задача кратчайшего расстояния не совсем имеет смысл. Более того, даже если у вас просто цикл с отрицательной суммой (не обязательно, что все ребра отрицательные) — то ситуация точно такая же.
Однако, ФБ позволяет находить такие циклы! Это шаг 3 в статье.
По идее, если вы принимаете ответ "минус бесконечность" как расстояние, то надо будет дополнить алгоритм каким-нибудь обходом в глубину или в ширину от всех вершин, расстояние до которых улучшилось уже после выполнения |V|-1 раундов улучшений по всем ребрам. Этим обходом вы пометите все вершины, до которых можно бесконечно крутиться, условно говоря, получая выгоду.
а по какому алгоритму сборщики мусора находят оторванные объекты?
Это разделение графа на компоненты связности. В простейшем варианте — BFS. Для направленных графов без циклов (такие графы обычно получаются при учёте объектов в памяти) — чуть сложнее, но в целом тоже нехитро (сначала найти корень проходом в обратную сторону против направления рёбер, а оттуда уже BFS).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Беллмана-Форда