En esta noticia
Cada vez que Google Maps te explica cómo llegar más rápido a tu destino, existe un algoritmo trabajando detrás, conocido frecuentemente como Dijkstra.
Si bien desde 1959 este funciono como la solución definitiva, un nuevo método logró superarlo en eficacia.
Cómo funciona el algoritmo Dijkstra
El algoritmo de Dijkstra funciona encontrando iterativamente el camino más corto desde un nodo de origen a todos los demás nodos en un grafo con pesos no negativos en sus aristas, utilizando una estrategia "voraz" para seleccionar el nodo no visitado con la menor distancia acumulada en cada paso.
El nuevo método que podría dejar atrás el algoritmo que le da vida a Google Maps
Un grupo de científicos presentó en ArXivun algoritmo que supera un límite teórico en grafos dirigidos con pesos reales no negativos.
El nuevo algoritmo propuesto por Duan, Jiayi Mao, Xiao Mao, Xinkai Shu y Longhui Yin busca acelerar la búsqueda de rutas en grafos dirigidos evitando la costosa operación de ordenar todos los nodos.
En lugar de mantener una cola de prioridad con todos los nodos, selecciona un pequeño grupo de elementos llamados pivotes y utiliza un enfoque de divide y vencerás para explorar el grafo de manera más eficiente.
La idea principal es reducir la cantidad de nodos que se deben considerar en cada paso. Con esto, el algoritmo solo trabaja con los candidatos más relevantes, lo que ahorra tiempo y mejora la eficiencia respecto con el algoritmo de Dijkstra.
Según los autores, es la primera vez que se supera teóricamente el límite de ordenamiento en grafos dirigidos de forma determinista.
El proceso se realiza en tres etapas principales:
Ejecutar rondas limitadas de Bellman-Ford para detectar nodos que se pueden completar rápidamente.
Elegir pivotes que cubran grandes subárboles, reduciendo los nodos necesarios para continuar.
Usar una estructura de datos con orden parcial, más simple y rápida que una cola de prioridad completa.
El subalgoritmo central, llamado BMSSP (Bounded Multi-Source Shortest Paths), permite resolver partes del grafo sin ordenar toda la lista de nodos, manteniendo límites de trabajo por nivel y acelerando el cálculo de rutas.
¿Por qué romper la barrera del ordenamiento es tan importante?
Lo que está en juego va más allá de un simple aumento de velocidad. El algoritmo desarrollado separa dos procesos que hasta ahora se realizaban conjuntamente: la determinación de las distancias mínimas y la ordenación de los vértices según esas distancias. Al desacoplarlos, el enfoque abre la posibilidad de explorar alternativas más eficientes en distintos escenarios.
Lo más significativo de este avance es que demuestra que aún era posible mejorar un algoritmo considerado prácticamente óptimo. Durante años se asumió que no se podía resolver este tipo de problemas de manera más eficiente sin comprometer la exactitud; el nuevo método prueba lo contrario: es factible ahorrar tiempo sin requerir suposiciones especiales ni métodos probabilísticos.
Asimismo, el algoritmo se desarrolla dentro del denominado modelo de comparación y suma, un marco muy general que solo permite operar mediante sumas y comparaciones sobre los pesos de las aristas.