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

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

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

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

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

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

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

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

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

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

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