История создания Алгоритма Дейкстры и его реализация на Python

Каждый студент, изучающий информатику, знает об алгоритме Дейкстры для поиска кратчайшего пути.

Но знаете ли вы, что этот культовый алгоритм был придуман в ресторане, да еще и за 20 минут?

Во время интервью в 2001 году Эдсгер Вайб Дейкстра рассказал, что разработал алгоритм всего за 20 минут во время шопинга в Амстердаме со своей невестой в 1956 году. 

Его вдохновил вопрос: 

“Каким кратчайшим путем можно добраться из Роттердама в Гронинген?”

Он спроектировал его без карандаша и бумаги. 

Алгоритм был опубликован три года спустя в трехстраничной статье под названием “Заметка о двух проблемах, связанных с графами”.

Дейкстра получил премию Тьюринга в 1972 году за фундаментальный вклад в разработку структурированных языков программирования, но алгоритм кратчайшего пути остается его самой известной работой.

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