Nuevo algoritmo supera método clásico para hallar rutas más cortas
Investigadores desarrollan un método que rompe la «barrera de ordenación» en redes, superando al algoritmo de Dijkstra. Esta innovación evita ordenar nodos por distancia y utiliza clústeres con elementos de Bellman-Ford para mayor eficiencia.
Nuevo algoritmo supera a Dijkstra en hallar rutas más cortas
Un equipo investigador ha desarrollado un método que rompe la «barrera de ordenación» en redes. Este avance computacional acelera la resolución de un problema fundamental en informática.
Avance en Ciencia Computacional
La investigación, dirigida por Ran Duan de la Universidad de Tsinghua, presenta un algoritmo que evita ordenar nodos por distancia. Esta innovación permite al método funcionar más rápido que el algoritmo clásico de Dijkstra, enseñado en libros de texto durante décadas.
Estrategia No Convencional
El algoritmo agrupa nodos en clústeres y utiliza selectivamente elementos de Bellman-Ford para identificar nodos influyentes. Este enfoque no siempre explora los nodos más cercanos primero, evitando así la limitación fundamental de ordenación.
Rompiendo Límites Establecidos
La «barrera de ordenación» había permanecido infranqueable durante cuarenta años para grafos con pesos arbitrarios. Robert Tarjan, coinventor del algoritmo más rápido anterior, calificó el resultado como «asombroso».
Colaboración Internacional
El desarrollo involucró a tres estudiantes de posgrado y a Xiao Mao de Stanford. Mao aportó una versión no aleatoria del algoritmo, combinando enfoques durante meses de trabajo colaborativo.
Implicaciones del Descubrimiento
Este avance abre nuevas posibilidades de optimización en redes de transporte, logística y comunicaciones. Los investigadores planean ahora simplificar el algoritmo para lograr mayores velocidades, ya que el método actual no está cerca de ningún límite fundamental conocido.