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.
Ainda não há comentários.