Алгоритм Дейкстры не работает, мое понимание должно быть ошибочным

Question

Вот моя интерпретация того, как алгоритм Дейкстры , как описано в википедии , будет иметь дело с приведенным ниже графиком.

Сначала он отмечает кратчайшее расстояние до всех соседних узлов, поэтому A получает 1 и Cполучает 7. Затем он выбирает соседа с текущим кратчайшим путем.Это A. Источник отмечен как посещенный и больше не будет рассматриваться.Самый короткий (и единственный) путь от источника до B через A теперь равен 12. A помечен как посещенный.Кратчайший путь от источника до пункта назначения через B составляет 13. B помечен как посещенный.Кратчайший путь от источника до C через пункт назначения равен 14, но это вдвое больше предыдущего кратчайшего пути к C, который равен 7, поэтому 14 отбрасывается.Пункт назначения теперь помечен как посещенный.

Пункт назначения отмечен как посещенный, поэтому алгоритм завершен.Вот результат:

Итак, я неверно истолковал описание?Является ли описание в Википедии неправильным?Или я как-то наткнулся на случай, который показывает, что алгоритм Дейкстры неверен (в чем я сильно сомневаюсь)?Я заметил, что выбранный путь, кажется, выбран жадным образом, но, очевидно, это одна из определяющих характеристик алгоритма, однако в этом случае он, похоже, дает неправильный результат.

Answer 1

Назначьте каждому узлу предварительное значение расстояния: установите его равным нулю для нашего начального узла и бесконечности для всех остальных узлов.Пометить все узлы как непосещенные.Установите начальный узел как текущий.Создайте набор не посещенных узлов, называемый не посещенным набором, состоящий из всех узлов, кроме начального узла.(Wiki)

Используя ваш пример:

Не посещено

A = inf;
B = inf;
C = inf;
Dest = inf;

Посещено

Origin = 0;

Для текущего узла:рассмотрите всех его не посещенных соседей и вычислите их предварительные расстояния.

O => A = 1;
O => C = 7;

Теперь мы находимся в A.

Из A единственный путь - B, это дает нам

O => AB = 12;
O => C = 7

C теперь является наименьшим расстоянием и является новым текущим узлом

O => CD = 8

Поскольку D - пункт назначения, а 8 <12, выбран маршрут CD. </p>

Answer 2

После посещения B общее пройденное расстояние составляет 12. 7 меньше, чем 12, и, следовательно, поиск возобновится в C.

Узел помечается как посещенный только после того, как все его соседи были рассмотрены.,В начале, источник помечается как посещенный и ему присваивается нулевое расстояние.Все остальные узлы помечены как не посещенные.

Answer 3

Затем он выбирает соседа с текущим кратчайшим путем.

Нет, он выбирает не посещенный узел с текущим кратчайшим путем.

Википедия пишет:

Установите не посещенный узел, помеченный наименьшим предварительным расстоянием, как следующий «текущий узел» и вернитесь к шагу 3.

Это не говорит, что это сосед.

А псевдокод из Википедии гласит:

 8      while Q is not empty:                  // The main loop
 9          u := vertex in Q with smallest distance in dist[] ;

где Q содержит все узлы, которые еще не посещались.