Отрицательные циклы во взвешенных орграфах: различия между версиями

Экспериментальное исследование задачи нахождения отрицательных циклов было проведено в [ ]; были использованы несколько методов, сочетающих алгоритм нахождения кратчайших путей (на основе подхода Беллмана-Форда) со стратегией обнаружения циклов, а также их более поздние разновидности. Оказалось, что эффективность работы алгоритмов нахождения отрицательных циклов зависит от количества и размера отрицательных циклов. В результате был получен набор семейств начальных условий для тестирования алгоритмов нахождения отрицательных циклов.

Продолжение данного исследования было опубликовано в работе [14]; в нем были представлены две новые эвристики, встроенные в три алгоритма, рассматривавшихся в [ 4 ] (исходный алгоритм Беллмана-Форда и его вариации, предложенные в [13] и [7]), что привело к значительному улучшению результатов. В [14] использовались те же наборы данных, что и в [4].