Отрицательные циклы с алгоритмом Дейкстры

Итак, я полностью понимаю, почему отрицательные веса ребер не будут работать с алгоритмом Дейкстры с таким примером:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

Однако я читал, что «если в графе есть какой-либо отрицательный цикл, вы никогда не перестанете обновлять расстояние в вершинах. Это вызовет бесконечный цикл». Я не понимаю, как это может быть, если мы объявляем вершины «готовыми», когда посещаем их. Как мы можем войти в цикл, если мы не можем вернуться к уже посещенным вершинам?


algorithm dijkstra bellman-ford negative-number
person Zack Martin    schedule 17.08.2018    source источник
comment
Зависит от того, как вы реализуете алгоритм. В графе без отрицательных ребер нет необходимости иметь отдельную переменную, которая помечает вершину как посещенную. Посещенный узел больше никогда не будет посещен просто потому, что он уже имеет кратчайшее возможное расстояние.   -  person user3386109    schedule 18.08.2018
comment
У Дейкстры есть важное свойство, на которое опирается каждое доказательство правильности: как только узел установлен, известен кратчайший путь к этому узлу. Однако, если у вас есть отрицательные веса, вы можете позже найти путь, который короче, т.е. улучшает стоимость. Затем вам нужно будет обработать узел и снова расслабить его дуги. Тогда свойство нарушается, и алгоритм больше не вычисляет кратчайший путь.   -  person Zabuzard    schedule 18.08.2018

Ответы (1)


arrow_upward
4
arrow_downward

Версия, которую вы описываете, действительно позволит избежать петель. Он также может не обнаружить правильный путь с наименьшей стоимостью в случаях, когда путь с наименьшей стоимостью имеет отрицательные ребра, но существует более прямой маршрут без них.

person btilly    schedule 18.08.2018