Как Dikjstra может найти кратчайший путь в этом графе?

Question

Мне трудно понять, как Дейкстра находит кратчайший путь (насколько я понимаю, работает) в следующем графике, если нам нужно найти кратчайший путь от 0 до 3: https://graphonline.ru/tmp/saved/SH/SHBqKyENwJqcCJGM.png

Если алгоритм выбирает наименьший вес из 0 и отмечает 0 как посещенный, разве он не выберет узел 1, а затем узел 3?как бы выбрать узел 2?

Answer 1

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

Алгоритм посетит узел 0 и добавит узлы 1 и 2 кочередь с приоритетами.Затем он посетит узел 1, поскольку он является ближайшим узлом в очереди с приоритетами, и добавит узел 3 в очередь с приоритетом на расстоянии 6. Узел 2 все еще находится в очереди, и поскольку он ближе к узлу 0, чем к узлу 3Посещение будет дальше.При посещении узла 2 будет найден более короткий путь длиной 4 до узла 3, поэтому расстояние до узла 3 будет обновлено до 4. Затем будет посещен узел 3.

Answer 2

По сути, Dijkstra можно использовать только для определения кратчайшего пути в данном взвешенном графе от одного исходного узла к каждому другому узлу в той же структуре данных графа, при условии, что узлы достижимы из исходного узла.Алгоритм работает до тех пор, пока не посетит все вершины графа.Кратчайший путь постоянно просматривается и обновляется.

Возможно, эта ссылка будет полезна для лучшего понимания самого алгоритма.https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e

Answer 3

Насколько я понимаю, алгоритм пересчитывает предварительные расстояния соседних, не посещенных, вершин, прежде чем выбрать следующую вершину для посещения. Когда вы находитесь на 1, вы сначала пересчитываете предварительное расстояние от соседних неповрежденных вершин, в данном случае 3. Затем выберите не посещенный узел с самым коротким предварительным расстоянием, в данном случае 2, и посетите этот узел.