[Перевод] Математики превзошли классический алгоритм поиска пути в графе

В поиске решения сложной задачи, часто помогает определённая организованность. Например, вы можете разбить задачу на части и сначала решить самые простые. Но такая сортировка имеет свою цену. В итоге вы можете потратить слишком много времени на то, чтобы расставить части по порядку.

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

"Кратчайший путь — это прекрасная задача, которую может понять любой человек в мире», — говорит Миккель Торуп, специалист по информатике из Университета Копенгагена.

Читать далее