“Es un gran algoritmo”, dijo Erik Demaineinformático del Instituto Tecnológico de Massachusetts. “Es muy rápido, simple y fácil de implementar”.
Para poner este procedimiento en práctica, necesitaría decidir sobre un sistema para organizar sus notas: una estructura de datos, en la jerga de la informática. Esto puede parecer un detalle técnico menor, pero el tiempo dedicado a buscar en sus notas cada vez que necesita editar o eliminar una entrada puede tener un gran efecto en el tiempo de ejecución general del algoritmo.
El artículo de Dijkstra utilizó una estructura de datos simple que dejaba margen de mejora. En las décadas siguientes, los investigadores desarrollaron otros mejores, cariñosamente llamados “montones”, en los que ciertos elementos son más fáciles de encontrar que otros. Aprovechan el hecho de que el algoritmo de Dijkstra sólo necesita eliminar la entrada del vértice restante más cercano. “Un montón es básicamente una estructura de datos que te permite hacer esto muy rápidamente”, dijo Václav Rozhoňinvestigador del Instituto de Ciencias de la Computación, Inteligencia Artificial y Tecnología (INSAIT) en Sofía, Bulgaria.
En 1984, dos informáticos desarrollaron un diseño de montón inteligente eso permitió que el algoritmo de Dijkstra alcanzara un límite teórico, o “límite inferior”, en el tiempo necesario para resolver el problema de los caminos más cortos de una sola fuente. En un sentido específico, esta versión del algoritmo de Dijkstra es la mejor posible. Esa fue la última palabra sobre la versión estándar del problema durante casi 40 años. Las cosas sólo cambiaron cuando algunos investigadores analizaron más de cerca lo que significa ser “mejor”.
Mejor comportamiento
Los investigadores suelen comparar algoritmos estudiando cómo funcionan en los peores escenarios. Imagine la cuadrícula de calles más confusa del mundo y luego agregue algunos patrones de tráfico especialmente desconcertantes. Si insistes en encontrar las rutas más rápidas en estas circunstancias extremas, la versión de 1984 del algoritmo de Dijkstra es demostrablemente imbatible.
Pero, con suerte, tu ciudad no tiene la peor red de calles del mundo. Entonces usted se preguntará: ¿Existe un algoritmo que sea imbatible en todas las redes de carreteras? El primer paso para responder a esta pregunta es asumir de forma conservadora que cada red tiene los peores patrones de tráfico. Luego desea que su algoritmo encuentre las rutas más rápidas a través de cualquier diseño de gráfico posible, asumiendo los peores pesos posibles. Los investigadores llaman a esta condición “optimidad universal”. Si tuvieras un algoritmo universalmente óptimo para el problema más simple de ir de un punto de un gráfico a otro, podría ayudarte a evitar el tráfico en las horas pico en todas las ciudades del mundo.
