Per oltre mezzo secolo, ricercatori di tutto il mondo hanno cercato di risolvere un problema algoritmico noto come “problema del percorso più breve da un’unica sorgente”. Si tratta, essenzialmente, di trovare in un grafo il percorso più breve tra un nodo e tutti gli altri nodi di una rete (in cui possono esserci anche connessioni con pesi negativi). Questo tipo di calcolo è già utilizzato in un’ampia gamma di app e tecnologie da cui dipendiamo per orientarci, come per esempio Google Maps, che ci guida attraverso paesaggi e città.

Ora, i ricercatori del Dipartimento di Informatica dell’Università di Copenaghen sono riusciti a risolvere il problema del percorso più breve da un’unica fonte, enigma che ha resistito per decenni. “Abbiamo scoperto un algoritmo che risolve il problema in un tempo quasi lineare, il modo più veloce possibile” ha spiegato Christian Wulff-Nilsen, tra gli autori dello studio postato su arXiv.

Lo scienziato ritiene che la soluzione del problema del percorso più breve da un’unica fonte potrebbe aprire la strada ad algoritmi che non solo aiutano le auto elettriche a calcolare il percorso più veloce da A a B in un istante, ma lo fanno nel modo più efficiente dal punto di vista energetico. “Stiamo aggiungendo una ‘dimensione’, cosa che gli algoritmi precedenti non hanno. Questa dimensione ci permette di guardare quelli che chiamiamo ‘pesi negativi’. Un esempio pratico; può essere utile considerare, in una rete stradale, che se hai un’auto elettrica questa si ricarica mentre si viaggia in discesa” aggiunge Wulff-Nilsen.

Lo scopo del problema del percorso più breve a sorgente singola è trovare i percorsi più brevi da un dato nodo di partenza a tutti gli altri nodi in una rete. La rete è rappresentata come un grafo costituito da nodi e connessioni tra di essi, detti archi. Ogni arco ha una direzione (per esempio, potrebbe rappresentare strade a senso unico), nonché un peso, che esprime quanto è costoso viaggiare lungo quel tratto. Se tutti i pesi degli archi sono non negativi, il problema può essere risolto in un tempo quasi lineare con il classico “algoritmo di Dijkstra”.
Il nuovo risultato trovato risolve il problema in quasi la stessa quantità di tempo dell’algoritmo di Dijkstra, ma consente anche pesi degli archi negativi. “In linea di principio, l’algoritmo potrebbe essere utilizzato, per esempio, per avvisare le banche centrali quando qualcuno sta speculando sull’acquisto e la vendita di varie valute”, continua Wulff-Nilsen.

Il ricercatore sottolinea che esistono già sistemi per calcolare sia la valuta, che i percorsi per le auto elettriche, ma la risoluzione del problema del percorso più breve della sorgente singola ha permesso ai ricercatori di creare un potente algoritmo che diventa quasi impossibile da battere in velocità. Allo stesso tempo, la sua semplicità lo rende facilmente adottabile per le diverse esigenze della società.