Estás en IA y tienes que ir a clase en HU. Tienes poco tiempo, así que sales apresurado por CN, cruzas un camino de árboles, pasas por Ágora y trotas con tu mochila puesta mientras atraviesas el Lumen, el K y la crepería. Cinco minutos y muchas vueltas después, finalmente encuentras tu salón. Te sientas afuera, aliviado y sudoroso, esperando a que comience la clase. Observando tus alrededores te preguntas: ¿y si había una ruta más corta?
En términos sencillos, un camino mínimo es la ruta más corta entre dos puntos en una red o grafo. Un grafo es una estructura matemática que consiste en nodos (que representan los puntos de interés) y aristas (líneas que conectan estos puntos). El problema del camino más corto consiste en encontrar una secuencia de nodos conectados por aristas, de tal manera que la suma de los pesos (distancias, tiempos, etc.) sea mínima.
A lo largo de la historia, se han desarrollado diversos algoritmos con el propósito de encontrar estos caminos mínimos. Uno de los más conocidos, el algoritmo de Dijkstra, fue desarrollado por Edsger W. Dijkstra en 1956, y funciona asignando una distancia infinita inicial a todos los nodos, a excepción del nodo origen, que se inicializa en cero. Luego, iterativamente, se actualizan las distancias mínimas a los nodos vecinos, seleccionando en cada paso el nodo no visitado que tenga la menor distancia.
Otra variante es el algoritmo A*, que incorpora una heurística para estimar la distancia restante al destino, permitiendo una búsqueda más eficiente en ciertos casos.
Imaginemos que representamos el Campus como un grafo. Cada edificio, cruce de caminos o punto de interés sería un nodo, y cada camino entre ellos sería una arista con un peso determinado por la distancia o tiempo estimado de recorrido. En varias universidades, ya se han implementado sistemas similares. Por ejemplo, en la UNAM se desarrolló un sistema web que aplica el algoritmo de Dijkstra para generar rutas óptimas dentro de Ciudad Universitaria, que tiene una extensión de más de 3 km². Aplicando el mismo algoritmo a un grafo del mapa de la UDLAP, podemos conocer el camino mínimo entre cualesquiera dos puntos, como se ilustra a continuación:
*Ruta más corta entre la entrada Gaos e IA, obtenida mediante la implementación de Dijkstra en Python y la librería OSMnx
Este enfoque no se limita al entorno universitario. Los mismos principios que permitirían encontrar la ruta más corta en nuestro campus son los que utilizan aplicaciones como Google Maps o Waze. Estas plataformas representan las calles y carreteras como grafos, donde las intersecciones son nodos y las vías son aristas con pesos determinados por distancias, tiempos estimados de recorrido, tráfico actual, etc.
Sin embargo, estos sistemas son mucho más complejos y utilizan variantes avanzadas de estos algoritmos, además de incorporar aprendizaje automático y datos en tiempo real para optimizar las rutas.
Aunque pareciera un simple problema cotidiano, decidir por dónde caminar entre clase y clase es, en realidad, un problema de optimización que puede resolverse con matemáticas y ciencia de datos. La próxima vez que sientas que diste demasiadas vueltas, recuerda: quizás la ruta más corta ya estaba ahí, solo necesitabas verla como un grafo.
Daniela Renée
Reportera de ciencias
daniela.ramirezgz@udlap.mx
Referencias
GeeksforGeeks. (2025). What is Dijkstra’s Algorithm? | Introduction to Dijkstra’s Shortest Path Algorithm. GeeksforGeeks. https://www.geeksforgeeks.org/introduction-to-dijkstras-shortest-path-algorithm/#dijkstras-algorithm
GeeksforGeeks. (2024). A* search algorithm. GeeksforGeeks. https://www.geeksforgeeks.org/a-search-algorithm/
Iturbide, J. (2006). Aplicación del Algoritmo de Dijkstra en un Sistema Web de Generación de Rutas para Ciudad Universitaria. https://ru.dgb.unam.mx/bitstream/20.500.14330/TES01000608659/3/0608659.pdf