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

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

Докладніше: Він зберігає найкращу відому відстань для кожного вузла. На кожному кроці бере незавершений вузол із найменшою попередньою відстанню й перевіряє, чи не стають шляхи до його сусідів коротшими через нього («релаксація»).