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

Коротко: Алгоритм Дейкстры находит в графе с неотрицательными весами рёбер кратчайший путь от начального узла до всех остальных.

Подробнее: Он хранит лучшее известное расстояние для каждого узла. На каждом шаге берёт незавершённый узел с наименьшим предварительным расстоянием и проверяет, не становятся ли пути к его соседям короче через него («релаксация»).