🦇27. Динамические структуры данных. Графы. Алгоритм Дейкстры для нахождения кратчайшего расстояния

от заданной вершины до всех остальных. Пример.

О графах и динамических структурах читайте здесь

Алгоритм Дейкстры

Задача алгоритма: поиск кратчайшего пути от исходной точки до любой другой вершины графа.

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

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

Фото с лекции

Псевдо-код

⭐Алгоритм Дейкстры понятным языком: начиная с 01:07

⭐Вес ребра может быть отрицательным, однако петля отрицательной быть не может.