Я знаю, что нет способа найти минимальное расстояние, когда на графике есть отрицательные весовые циклы, не будет никакого значения минимального расстояния. Мой вопрос: что произойдет, если мы скормим алгоритму Флойда Уоршалла графами с отрицательными весовыми циклами? Будет ли он работать бесконечно или завершится (возможно, с неправильным ответом) за O(n3)?
Временная сложность алгоритма Флойда Уоршалла на отрицательных весовых циклах
Ответы (1)
Как вы можете найти в Википедии
Алгоритмы Флойда-Уоршалла, основанные на текущем или максимальном весе.
Алгоритмы просто проходят через все пары вершин и вычисляют расстояние. Так что ответ - Нет, он не будет работать бесконечно.
И определенно алгоритм вернет неправильный ответ (для вершин в отрицательных циклах у вас будут отрицательные расстояния). Например, расстояние от вершины до самой себя будет отрицательным.
Также этот алгоритм можно использовать для обнаружения отрицательных циклов.
person
Laser
schedule
20.03.2017
