Алгоритм dijkstras режет края кратчайшего пути по порядку?

В упражнении "Введение в алгоритмы, 3-е издание" 24.3-5 требуется пример того, что это неправильно (не всегда верно). Это возможно? По моему мнению, это невозможно, потому что каждое ребро расслабляется в то время, когда путь к текущей вершине уже решен.

Слово за слово:

Профессор Н. утверждает, что имеет доказательство правильности алгоритма Дейкстры. Он утверждает, что алгоритм Дейкстры релаксирует ребра каждого кратчайшего пути в графе в том порядке, в котором они появляются на пути, и поэтому свойство релаксации пути применяется к каждой вершине, доступной из источника. Покажите, что профессор ошибается, построив ориентированный граф, для которого алгоритм Дейкстры может ослабить ребра кратчайшего пути не в порядке.

Ответ 1

Я думаю, что ключевая фраза в формулировке заключается в том, что алгоритм dijkstra "релаксирует ребра каждого кратчайшего пути в графе..."

Это само по себе является ложью, если существует несколько кратчайших путей одной и той же стоимости.

Рассмотрим этот график: A → B, A → C, B → D, C → D. Источник - это A, а Destination - D. Каждый вес края равен 1. Есть два пути от A до D, один через B и один через C. Однако один ребро B- > D или C- > D никогда не расслабляется.

Все еще не убежден, потому что dijkstra заканчивается перед оценкой другого ребра в D? Бросьте в дополнительный край D- > E и установите Destination в E. Путь от A- > D до B будет такой же, как и A- > D-C, и они дешевле, чем стоимость A- > E. Однако вы никогда не будете расслаблять второй край в D, поскольку алгоритм только релаксирует ребра к вершинам, что он еще не знает кратчайший путь к.

Ответ 2

Рассмотрим следующий ориентированный граф: (A, B), (A, C), (B, D), (C, D), (D, E) с весами ребер w (A, B) = 1, w (A, C) = 1, w (B, D) = 0, w (C, D) = 0, w (D, E) = 1. Исходная вершина равна A. Возможная перестановка ребер, Алгоритм Дейкстраса (A, B), (A, C), (B, D), (D, E), (C, D). Кроме того, после выполнения алгоритма Дейкстры, A.d = 0, B.d = 1, C.d = 1, D.d = 1, E.d = 2. Существует два кратчайших пути от A до E, один - ABDE, а другой - ACDE. Противоречие ко второму пути, ребро (C, D) должно всегда расслабляться до (D, E).

Ответ 3

Дело в том, что вывод не вытекает из предпосылок и конструировать контрпример. SSSP находит все кратчайшие пути. Нет причин, чтобы кратчайшие пути были найдены в строгом порядке. Рассмотрим древовидный граф. Все пути также коротки. Теперь, если мы расслабим корень, то на краях нет особого порядка. Но предположим, вы даже навязывали. Затем, после расслабления ближайшего non-root node, у вас может быть множество очень длинных краев для второго уровня. Следующий ближайший корень-сосед может иметь кучу действительно коротких исходящих краев для этой части второго уровня. В этом случае вы расслабляете края, которые вносят свой вклад в общую длину пути SHORTER, чем другие края, которые вы уже расслабились, поскольку вы всегда расслабляете NODES, не ребрами в порядке кратчайшего пути.

Ответ 4

Рассмотрим график:

    A--->B  A--->C  B--->C  C--->D

и пусть каждое ребро имеет вес 0.

Алгоритмы Дейкстры могут ослабить ребра в порядке

    (A,C) (A,B) (C,D) (B,C)

График имеет два кратчайших пути от A до D, оба из которых стоят 0.

    A-->B-->C-->D   or   A-->C-->D

Ребра кратчайшего пути {A → B → C → D} ослаблены не по порядку, так как (B, C) ослабляется ПОСЛЕ (C, D).

Ответ 5

Создайте единый край, вес три, который достигнет места назначения. Теперь добавьте путь, состоящий из нескольких остановок, общий вес менее трех, которые также доходят до места назначения. Когда вы расслабляете происхождение, вы будете окрашивать пункт назначения node как три, что неверно. Вы должны продолжить расслабление всех узлов ближе, чем (min известный путь к месту назначения), пока этот набор не будет пустым. Только тогда вы можете быть уверены, что алгоритм D дал вам правильный ответ.

Посмотрите алгоритм A * для большего удовольствия.