Ricercatori di Tsinghua hanno ideato un nuovo algoritmo per il problema del percorso minimo single-source più veloce di Dijkstra.
Il nuovo metodo riduce la complessità a O(m·log^(2/3) n) superando la barriera di ordinamento O(m + n log n) di Dijkstra.
Il procedimento sfrutta raggruppamento di nodi di frontiera, rappresentanti chiave, rilassamenti in stile Bellman-Ford e divide-and-conquer ricorsivo.
Il vantaggio emerge soprattutto in grandi reti sparse, con applicazioni in navigazione su larga scala, routing di rete, IA e analisi di grafi complessi.
Limiti: prestazioni inferiori su grafi piccoli, implementazione complessa e non ancora sostituisce algoritmi specializzati o euristiche come A*.
La scoperta rappresenta un importante traguardo teorico, dimostrando che la barriera di ordinamento di Dijkstra non è insuperabile.
Get notified when new stories are published for "Hacker News 🇮🇹 Italiano"