Этот новый алгоритм работает быстрее только для разреженных графов (немного рёбер на вершину). Например, граф с 10^7 вершинами и всего 1-2 рёбрами на вершину может быть в 2-3 раза быстрее. Очень круто!
Deedy
Deedy8 авг., 23:30
Огромное достижение в области компьютерных наук: Профессор Цинхуа ТОЛЬКО что открыл самый быстрый алгоритм поиска кратчайшего пути для графов за 40 лет. Это улучшает алгоритм Тарьяна, лауреата премии Тьюринга, O(m + nlogn) с алгоритмом Дейкстры, который изучает каждый студент компьютерных наук в колледже.
1,52K