Pesquisadores da Universidade Tsinghua, na China, em colaboração com a Universidade Stanford, alcançaram um grande avanço em termos de complexidade computacional para o problema tradicional de caminho mais curto de fonte única (single-source shortest path, SSSP). Este trabalho recebeu o prêmio de Best Paper na STOC 2025.
Tradicionalmente, o método mais usado é o algoritmo de Dijkstra, cuja complexidade de tempo tem a forma O(m + n log n) (n = número de nós, m = número de arestas).
O termo log n está relacionado a partes envolvendo fila de prioridade (priority queue) ou ordenação (sorting), e não houve melhorias que superassem essa parte nos últimos 40 anos.
O novo algoritmo reduziu a complexidade de tempo para O(m · log^(2/3) n).
Como log^(2/3) n cresce mais lentamente do que log n (ou seja, aumenta menos do que log n), a diferença se torna maior quando o número de nós é muito grande.
18 comentários
Isso me faz lembrar dos tempos, lá no fim dos anos 2000, quando eu trabalhava numa empresa de software de navegação veicular desenvolvendo um módulo de busca de rotas.
O Dijkstra é lento demais para busca de rotas em navegação, então não se usa; em vez disso, usa-se o A* (A Star), uma versão aprimorada com heurística. Fui pesquisar e vi que o A* não é um algoritmo de SSSP, e sim de SPSP (Single-Pair Shortest Path).
Acho meio discutível dizer que superou o algoritmo mais rápido para casos esparsos.
O CLRS não foi revisado há tanto tempo assim; já vão lançar uma edição nova?
Parece a sensação de sair um novo álbum dos Beatles ou do Oasis, bandas que surgiram no passado e continuam populares até hoje, depois de 41 anos. Primeiro vem o espanto e a curiosidade, haha.
Talvez os EUA já tivessem um? Caramba...
Lindo demais, pqp
A China está avançando bastante ultimamente.
Como será que vão decidir o nome do algoritmo?
Daqui a pouco alguém vai criar um problema no Baekjoon com essas restrições, já estou até ansioso
Saudades do Dijkstra..
Uau... isso é incrível...
Muito legal.
Uau......
Isso é possível mesmo...
Uau~~
Uau....
Parece que vão ter que atualizar o conteúdo das aulas de algoritmos kkk
Nossa...