Выполняет ли алгоритм dijkstras по краям кратчайшего пути?

Question

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

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

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

Answer 1

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

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

Рассмотрите этот график: A -> B, A -> C, B -> D, C -> D. Источник - это A, а пункт назначения - 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, так как алгоритм только релаксирует ребра к вершинам, что он еще не знает кратчайшего пути.

Answer 2

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

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

Answer 3

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

Answer 4

Рассмотрим следующий ориентированный график: (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).

Answer 5

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

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

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

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

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

граф имеет две кратчайшие пути из От А до D, оба из которых стоили 0.

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

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