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

Question

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

Слово в слово:

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

Answer 1

Рассмотрим следующий ориентированный граф: (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).Кроме того, Ad = 0, Bd = 1, Cd = 1, Dd = 1, Ed = 2 после выполнения алгоритма Дейкстры.Существует два кратчайших пути от A до E, один из которых - ABDE, а другой - ACDE.Противоречие со вторым путем, ребро (C, D) всегда должно быть ослаблено до (D, E).

Answer 2

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

    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).

Answer 3

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

Answer 4

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

Одно это ложь, если есть несколько кратчайших путей одинаковой стоимости.

Рассмотрим этот график: 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 5

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

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