Датский математик Кристиан Вульф-Нильсен и двое его коллег смогли придумать алгоритм для выявления самого короткого пути между двумя точками. К сожалению, имеющаяся информация не изобилует подробностями.
Видимо, речь идёт о какой-то разновидности этого алгоритма, так как обычная задача нахождения кратчайшего пути давно решена (широко известный алгоритм A*, используемый, например, в стратегических играх и навигаторах). Эта задача в полном варианте требует больших вычислительных ресурсов. Время поиска решения в общем случае достаточно велико, могут не справиться даже современные суперкомпьютеры. Есть также упрощённые решения, необязательно дающие самый оптимальный вариант, но заметно более быстрые.
По всей видимости, какую-то разновидность этой задачи учёные не могли решить сорок лет. В Копенгагенском университете нашли алгоритм в общем виде, который требует не так много ресурсов. Правда, алгоритм A* считается оптимальным. Возможно, задачи решены при разных предположениях.
Во всех подобных задачах карта представляется в виде множества вершин (узловых точек, например, перекрёстков) и соединяющих их отрезков с некоторым параметром (обычно длиной этого участка дороги или временем её преодоления). Такая структура называется в дискретной математике графом. Есть два варианта этой математической абстракции (один рассматривает однонаправленные дороги, другой двунаправленные).
Вроде учёные научились решать задачу при динамически меняющемся графе. То есть когда некоторые пути могут оказаться недоступными или очень медленными (например, появление автомобильной пробки). Имеющиеся решения используют статический граф, но это не сильно портит их результат, так как решение находится достаточно быстро и при изменении ситуации алгоритм просто запускается повторно.
