Графы и пути — алгоритм Дейкстры

Зачем

В 1959 году Эдсгер Дейкстра пришел к выводу о том, что компьютеры могут находить самые эффективные траектории, измеряя и высчитывая расстояния в графе. Алгоритм этот крайне важен, хотя бы потому, что определение кратчайшего пути помогает туристам выстраивать наиболее «вместительные» маршруты.

Данная концепция до сих пор активно используется во многих приложениях для отрисовки маршрутов на картах.

Что

Начнем с развития интуитивного определения кратчайшего маршрута.

Определим кратчайший путь из SD.