В алгоритме Дейкстры, почему он должен сначала расширить узлы с текущей наименьшей стоимостью?

Question

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

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

Answer 1

Если вы развернете любой узел, вы в конечном итоге найдете какой-то путь к цели, но вы не сможете гарантировать оптимальную стоимость пути к цели.

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