2026/09/27

A louca complexidade de encontrar o caminho mais curto num mapa

Encontrar o caminho mais curto entre dois pontos num mapa é algo mais difícil do que pode parecer à primeira vista.

Há coisas que fazemos diariamente de forma corriqueira, sem pensar na louca complexidade que se esconde por trás. É isso que acontece quando recorremos a algo como o Google Maps ou app de navegação como o Waze, e pedimos para nos indicar a melhor rota até um ponto de destino.

Embora muitos dos que agora lêem o Aberto até de Madrugada não tenham tido a oportunidade de encetar longas viagens pelo país tendo que recorrer aos mapas em papel - e esperar que aquele mapa com alguns anos ainda estivesse actualizado, ou recorrer ao tradicional "parar para perguntar indicações sobre o caminho a seguir" - coisas que agora ficaram obsoletas graças aos mapas digitais e apps de navegação GPS, não deixará de ser curioso pensar que este problema era algo que já atormentava algumas pessoas em meados do século passado: mais concretamente, Edsger Dijkstra, que acabou por criar aquilo o Algoritmo de Dijkstra que ainda hoje está na base do funcionamento dos serviços de navegação que usamos.


Como dizia Arthur C. Clarke, qualquer tecnologia suficientemente avançada é indistinguível da magia. Isso é algo que assenta que nem uma luva a este caso, em que simplesmente escolhemos um destino e "magicamente" surge uma rota no ecrã e as instruções sobre o caminho a seguir.

Só que, não temos que agradecer os resultados a um Merlin ou David Copperfield, mas sim a Edsger Dijkstra.

Sem comentários:

Enviar um comentário (problemas a comentar?)