Почему алгоритм Дейкстры не работает с отрицательными рёбрами и что использовать вместо него?
Короткий ответ: жадный выбор «замораживает» вершины, предполагая, что найденные расстояния минимальны; с отрицательными рёбрами это нарушается. Используйте Беллмана–Форда (O(VE)) для отрицательных рёбер и детекции отрицательных циклов или Джонсона для всех пар на разреженных графах. Кстати, у нас сейчас действует 40% скидка на курс Алгоритмы и структуры данных.
🤖 Осталось 4 места на курс по ИИ-агентам. Набор закрывается 30 апреля.
🔗 Успеть на обучение
Библиотека собеса по С#
Post #1087
1.56K