Ограничения на алгоритмы Дейкстры, Беллмана и топологического алгоритма кратчайшего пути?
Какие точные ограничения / условия существуют, чтобы можно было использовать любой из этих трех алгоритмов SPT на графах для вычисления кратчайших путей?
1 ответ
Решение
Алгоритм Дейкстры требует, чтобы длины ребер были неотрицательными, в то время как Беллман-Форд требует только отсутствия циклов отрицательной длины.