я думаю, все, у кого был курс "Алгоритмы и структуры данных", на всю жизнь запомнили, что есть два алгоритма для нахождения кратчайших путей в графе - Дийкстры (на картинке) и Беллмана-Форда; многие помнят их сложности - O(m + n log n) и O(mn) соответственно; так вот у меня для вас есть новость, группа китайских товарищей изобрела алгоритм, который для направленных графов с неотрицательными весами ребер дает O(m (log n)^{2/3}), то есть существенно быстрее для больших и/или разреженных графов суть подхода состоит в том, чтобы иерархически разбить граф на несколько подграфов, в каждом из которых можно сократить количество проверяемых вершин до 1/(log n) похоже, пора вводить тег #алгоритмы, потрясения основ учащаются @valuableai
привет всем любителям посчитать гномиков на ночь с утра
3 дня назад3 дня назад
1
~1 мин