Por mais de meio século, pesquisadores de todo o mundo têm lutado com um problema algorítmico conhecido como "o problema do caminho mais curto de fonte única". O problema é essencialmente sobre como elaborar uma receita matemática que melhor encontre a rota mais curta entre um nó e todos os outros nós de uma rede, onde pode haver conexões com pesos negativos.

Parece complicado? Possivelmente. Mas, na verdade, esse tipo de cálculo já é usado em uma ampla variedade de aplicativos e tecnologias dos quais dependemos para encontrar nossos caminhos, pois o Google Maps nos guia por paisagens e cidades, por exemplo.

Agora, pesquisadores do Departamento de Ciência da Computação da Universidade de Copenhague conseguiram resolver o problema do caminho mais curto de fonte única , um enigma que deixou pesquisadores e especialistas perplexos por décadas.

"Descobrimos um algoritmo que resolve o problema em tempo praticamente linear, da maneira mais rápida possível. É um problema algorítmico fundamental que vem sendo estudado desde a década de 1950 e ensinado em todo o mundo. Esse foi um dos motivos que nos levou a resolver isso", explica o professor associado Christian Wulff-Nilsen, que claramente acha difícil deixar um problema algorítmico não resolvido sozinho.

No ano passado, Wulff-Nilsen fez outro avanço na mesma área, que produziu um resultado que abordava como encontrar o caminho mais curto em uma rede que muda ao longo do tempo. Sua solução para o enigma recente baseia-se nesse trabalho.

O pesquisador acredita que resolver o problema do caminho mais curto de fonte única pode abrir caminho para algoritmos que não apenas ajudem os carros elétricos a calcular a rota mais rápida de A a B em um instante, mas também o façam da maneira mais eficiente em termos de energia.

"Estamos adicionando uma dimensão que os algoritmos anteriores não têm. Essa dimensão nos permite olhar para o que chamamos de pesos negativos. Um exemplo prático disso pode ser com referência às colinas em uma rede rodoviária, o que é bom saber se você tem um carro elétrico que carrega durante a descida", explica Wulff-Nilsen.

Fatos sobre o problema do caminho mais curto de fonte única

O objetivo do problema do caminho mais curto de fonte única é encontrar os caminhos mais curtos de um dado nó inicial para todos os outros nós em uma rede.

A rede é representada como um grafo composto por nós e conexões entre eles, chamados de arestas.

Cada aresta tem uma direção (por exemplo, isso pode ser usado para representar estradas de mão única), bem como um peso, que expressa o quão caro é viajar ao longo dessa aresta. Se todos os pesos das arestas forem não negativos, o problema pode ser resolvido em tempo virtualmente linear com um algoritmo clássico de Dijkstra.

O novo resultado resolve o problema quase na mesma quantidade de tempo que o algoritmo de Dijkstra, mas também permite pesos de aresta negativos.

"Em princípio, o algoritmo pode ser usado para alertar atores, como bancos centrais , se os especuladores estiverem especulando sobre a compra e venda de várias moedas. Muito disso acontece usando computadores hoje. Mas, como nosso algoritmo é tão rápido, pode ser capaz de para ser usado para detectar brechas antes de serem exploradas", diz Christian Wulff-Nilsen.

A pesquisadora ressalta que já existem sistemas de cálculo tanto de moeda quanto de rotas para carros elétricos. Mas resolver o problema do caminho mais curto de fonte única permitiu que os pesquisadores criassem um algoritmo excelente que se torna quase impossível de vencer em relação à velocidade. Ao mesmo tempo, sua simplicidade facilita a adoção para as diversas necessidades da sociedade.

O trabalho para resolver o problema não passou despercebido. De fato, Christian Wulff-Nilsen e seus colegas já foram contatados por pessoas de todo o mundo querendo parabenizá-los e descobrir mais sobre como eles fizeram isso.

Ao mesmo tempo, o artigo de pesquisa que detalha sua descoberta foi homenageado com um "prêmio de melhor artigo" na conferência FOCS (Foundation of Computer Science) em Denver, Colorado.

"Pessoas de todo o mundo participam desta conferência para ver os melhores resultados sendo apresentados", diz Christian Wulff-Nilsen.

A pesquisa foi realizada em uma colaboração entre Christian Wulff-Nilsen, do Departamento de Ciência da Computação, Danupon Nanongkai do Instituto Max Planck e seu colega americano Aaron Bernstein da Universidade Rutgers.

A pesquisa está atualmente disponível no arXiv .