Алгоритм Дейкстры - sergeresko/Lem_in-explanation GitHub Wiki

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

Переменные

Комната r и множество S.

Инициализация

У всех комнат distance = ∞ и parent = NULL.

r равна start и у неё distance = 0.

Множество S пустое.

Пока `r ≠ NULL` и `r ≠ end`:

пройтись по соседям комнаты r, заменяя их distance на r->distance + link->weight, если эта сумма меньше, чем distance; при этом каждому содеду, которому понадобилась такая замена, присвоить parent = r и добавить этого соседа в множество S;
удалить из множества S комнату с наименьшим distance и обозначить её r.

Комментарий

Фраза «добавить комнату в множество» подразумевает, что, если эта комната уже находится в множестве, то добавления не происходит. Множество не может содержать повторяющихся элементов.