Правильно ли я понимаю алгоритм Дейкстры?

Question

Рассмотрим следующий взвешенный ориентированный граф:

Давайте рассмотрим узел 1 как начальный узел, в соответствии с алгоритмом Дейкстры у нас есть следующие шаги:

1. узел 1 отмечен как посещенный.

2. кратчайший путь к узлу 2 имеет вес 1. Отметить посещение узла 2.

3. кратчайший путь к узлу 3 имеет вес 30. Отметить посещенный узел 3. После этого согласно алгоритму узел 3 имеет минимальный вес пути, равный 30, и не может быть изменен. Но, очевидно, кратчайший путь к узлу 3 равен 4.

Не могли бы вы указать на какой-либо недостаток в моей интерпретации алгоритма?

Answer 1

В следующей таблице указаны все шаги алгоритма. Первый столбец показывает узел, который посещен, второй столбец показывает узлы, которые уже были исследованы (но еще не посещены), а также соседи текущего посещенного узла. Все узлы представлены в виде триплетов (n, d, p), где n - это имя узла, d - это расстояние от начального узла, а p - это узел-предшественник. Как уже упоминались другие ответы и комментарии, вы всегда будете посещать исследуемый узел с минимальным расстоянием:

visited node | explored nodes
-------------+-------------------------
(1, 0, -)    | (2, 1, 1) (3, 30, 1)
(2, 1, 1)    | (3, 30, 1) (4, 2, 2)
(4, 2, 2)    | (3, 30, 1) (5, 3, 4)
(5, 3, 4)    | (3, 4, 5)     //distance of node 3 is updated
(3, 4, 5)    | 

Следовательно, путь к узлу 3 фактически проходит по всем остальным узлам, как и ожидалось.

Answer 2

Короткий ответ - нет, ваше понимание неверно.

Вот правильный алгоритм:

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

Источник: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

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