Por: Gino Marín
Publicado el: 23 de junio de 2026
Colaboración Académica para la Universidad CENFOTEC.
Imagine la escena: Ámsterdam, una mañana de 1956. Un joven de 26 años acaba de recorrer tiendas con su prometida y, cansados los dos, se sientan en la terraza de un café. Él no trae papel. Tampoco lápiz. Mientras el café se enfría, resuelve de memoria un problema que le venía dando vueltas: ¿cuál es la ruta más corta entre dos ciudades?
Veinte minutos. Eso le tomó a Edsger Dijkstra diseñar el algoritmo que hoy lleva su apellido y que, setenta años después, sigue trabajando calladito cada vez que usted abre Waze, cada vez que un correo suyo cruza medio planeta por fibra óptica, cada vez que un personaje de videojuego rodea una pared sin chocar con ella.
Lo curioso es que Dijkstra ni siquiera buscaba resolver un gran misterio matemático. Necesitaba una demostración vistosa para presentar en sociedad una computadora nueva, la ARMAC, y quería un problema que cualquier persona entendiera sin estudiar ingeniería: ir de Róterdam a Groninga por el camino más corto. Años más tarde confesó, con algo de picardía, que el algoritmo quedó tan limpio justamente porque lo pensó sin lápiz: la falta de papel lo obligó a evitar toda complejidad innecesaria.
La gota de tinta
¿Y cómo funciona? Piense en un mapa como una red de puntos (ciudades, esquinas, enrutadores) unidos por líneas que tienen un costo: kilómetros, minutos, peajes. Dijkstra propuso algo de una sencillez casi terca: desde el punto de partida, atienda siempre primero al lugar más cercano que todavía no haya visitado. Anote cuánto costó llegar ahí, revise a sus vecinos, y repita.
El resultado se parece a una gota de tinta cayendo en agua quieta. La mancha se expande pareja, en círculos, y cuando toca el destino usted tiene una garantía hermosa: nadie pudo haber llegado por un camino más barato, porque todos los caminos más baratos ya fueron explorados antes.
Esa paciencia es su mayor virtud y también su factura. La tinta se expande hacia todos lados por igual, incluso en dirección contraria a donde usted quiere ir. Si el destino está al este, Dijkstra explora el oeste con el mismo entusiasmo. Para una computadora de 1956 alcanzaba de sobra. Para un robot que necesita decidir en tiempo real, no tanto.
Un robot tembloroso entra en escena
Demos un salto: California, finales de los años sesenta. En el Stanford Research Institute, un equipo construye el primer robot móvil capaz de razonar sobre sus propias acciones. Se movía con tantas sacudidas que, tras un mes buscando nombres elegantes, alguien se rindió ante lo evidente y lo bautizaron Shakey: el tembloroso.
Shakey tenía que planear rutas entre cuartos llenos de obstáculos, y la computadora que lo pensaba todo (del tamaño de un cuarto, dicho sea de paso) no podía darse el lujo de inundar el mapa entero como la tinta de Dijkstra. Tres investigadores —Peter Hart, Nils Nilsson y Bertram Raphael— encontraron la salida en 1968, y la publicaron con un nombre que parece broma de matemáticos: A* (se lee «A estrella»).
La idea es darle al algoritmo algo que Dijkstra no tenía: una corazonada. Para decidir qué punto explorar después, A* suma dos números. El primero es el costo real acumulado desde la salida, lo que ya gastó. El segundo es una estimación de lo que falta hasta la meta, por ejemplo la distancia en línea recta. Memoria más intuición. Lo vivido más lo esperado.
Con esa brújula, la mancha de tinta deja de ser un círculo y se estira como una flecha apuntando hacia el destino. El algoritmo sigue revisando alternativas, sigue siendo cuidadoso, pero deja de perder el tiempo en direcciones absurdas.
Y aquí viene el detalle fino, el que separa este truco de una simple apuesta: si la estimación es optimista —si nunca exagera lo que falta, como la línea recta, que jamás es más larga que el camino real— A* conserva la misma garantía de Dijkstra. Encuentra el mejor camino, palabra de honor, pero visitando una fracción de los lugares.
Dijkstra (izquierda) y A (derecha) resolviendo la misma cuadrícula al mismo tiempo: Dijkstra pinta anillos concéntricos en todas direcciones, mientras A deja un rastro en forma de cometa apuntando hacia la meta.
Misma cuadrícula, mismo camino óptimo: a la izquierda la onda de Dijkstra; a la derecha la flecha de A. Lo que cambia es cuántas celdas visita cada uno.*
¿Rivales? Más bien parientes
Después de tantos años explicando esto en clase, le confieso cuál es el momento que más disfruto: cuando alguien descubre que no son dos algoritmos distintos. Si a A* le apaga la intuición —si su estimación de lo que falta es siempre cero— se comporta exactamente igual que Dijkstra. Uno es el caso particular del otro. El estudiante humilde y el estudiante con buenos presentimientos resuelven el examen con el mismo método; la diferencia es cuánto borrador gastan.
El visualizador con la heurística de A puesta en cero: ambos paneles exploran exactamente las mismas celdas, demostrando que A sin corazonada es idéntico a Dijkstra.
El experimento que ningún teorema reemplaza: con la heurística en cero, A (derecha) explora las mismas celdas que Dijkstra (izquierda). Son la misma idea, con y sin brújula.*
¿Cuándo usar cada uno, entonces? Dijkstra brilla cuando no hay una meta única: calcular distancias desde un punto hacia todos los demás, como hacen los protocolos que enrutan el tráfico de internet. A* gana cuando hay un destino claro y alguna forma razonable de estimar qué tan lejos queda: mapas, videojuegos, robótica. No es casualidad que los vehículos que hoy ruedan sobre Marte naveguen con un descendiente directo de A*; a esa distancia, nadie puede manejarlos con control remoto.
Tampoco son perfectos. Ninguno de los dos tolera costos negativos (esas rarezas existen, y tienen su propio algoritmo), y A* es tan bueno como la corazonada que usted le dé: una estimación que exagera lo devuelve rápido pero mentiroso.
La próxima vez que su aplicación de mapas recalcule la ruta en dos segundos, acuérdese de esta historia. Ahí adentro hay un café de Ámsterdam de 1956 y un robot tembloroso de los sesenta, todavía trabajando juntos, todavía discutiendo amablemente si conviene la paciencia o la intuición.
Casi siempre, la respuesta es: un poco de las dos.
—
¿Quiere verlos correr con sus propios ojos? No se quede con la descripción: construí tres visualizadores interactivos para que los vea pensar, y cada uno sube una dimensión.
Pruébelo con sus propios ojos
En el plano (2D). El clásico: una cuadrícula donde puede dibujar muros, sembrar terrenos pesados, mover el origen y la meta, y ver a los dos algoritmos correr lado a lado (son las imágenes de más arriba). Cambie la heurística a «cero» y vea a A* convertirse en Dijkstra en vivo. → Abrir el visualizador 2D
En el espacio (3D). El mismo duelo, pero dentro de un laberinto de verdad, con volumen. Aquí Dijkstra infla una burbuja de luz que llena el cubo mientras A* perfora un túnel directo hacia la meta; puede orbitar la escena y hasta rebanar el laberinto capa por capa para ver la búsqueda por dentro.
Laberinto volumétrico en 3D: Dijkstra (izquierda) llena el cubo con una burbuja de luz, mientras A (derecha) perfora un túnel dirigido hacia la meta.
A través del tiempo (4D). Y la edición que más me gusta: el tiempo como una dimensión más. El tablero es plano, pero cada capa hacia arriba es un instante; hay muros que patrullan y trazan paredes en diagonal, y esperar —quedarse quieto mientras el obstáculo pasa— se vuelve una jugada válida. El plan óptimo es una línea que a veces sube en vertical: ese es el algoritmo decidiendo aguardar.
Diagrama de espacio-tiempo en 4D: el eje vertical es el tiempo, los obstáculos móviles trazan paredes diagonales, y el camino sube en vertical en los instantes en que conviene esperar.
→ Abrir el visualizador 4D (espacio-tiempo)
Y si le quedó gusto, la versión extendida de este artículo entra en el detalle técnico: pseudocódigo, implementaciones en Python, análisis de complejidad, el truco de expandir el grafo en el tiempo y los errores clásicos que todos hemos cometido al programarlos.
Msc. Gino Marín L. escribe sobre algoritmos, inteligencia artificial e ingeniería de software. Esta entrega forma parte de la serie Entendiendo algoritmos.
