Algoritmo de Dijkstra: el camino más corto explicado paso a paso
Cada vez que Google Maps te dice la ruta más rápida, hay un algoritmo de grafos detrás. Dijkstra es el más clásico de todos y uno de los más importantes de la informática. Entenderlo abre las puertas a GPS, redes de distribución, videojuegos y mucho más.
El problema que resuelve
Dado un grafo con nodos (ciudades, intersecciones, routers) y aristas con pesos (distancias, tiempos, costes), encuentra el camino de menor coste desde un nodo origen a todos los demás. Condición: los pesos deben ser no negativos.
Cómo funciona paso a paso
1. Asigna distancia 0 al nodo origen y ∞ a todos los demás.
2. Marca el nodo origen como "no visitado" y lo pones en una cola de prioridad.
3. Extrae el nodo con menor distancia acumulada.
4. Para cada vecino no visitado, calcula si el camino pasando por el nodo actual es más corto que el conocido hasta ahora. Si sí, actualiza.
5. Marca el nodo como visitado. Repite desde el paso 3 hasta visitar todos.
Complejidad
Con una cola de prioridad (min-heap): O((V + E) log V), donde V son vértices y E aristas. Suficiente para grafos con millones de nodos en tiempo real.
Limitaciones
Dijkstra no funciona con pesos negativos — para eso existe Bellman-Ford. Tampoco encuentra el camino más corto entre todos los pares de nodos de forma eficiente — para eso está Floyd-Warshall.
Aplicaciones reales
Navegación GPS, protocolo de enrutamiento OSPF en redes IP, cálculo de rutas en videojuegos (combinado con A*), sistemas de distribución logística.
Preguntas frecuentes
¿Cuál es la diferencia entre Dijkstra y A*?
A* es Dijkstra con una heurística que estima la distancia restante al destino. Es más eficiente cuando conoces el destino específico (como en GPS) porque dirige la búsqueda hacia él en vez de explorar en todas las direcciones.
¿Por qué no funciona con pesos negativos?
Porque una vez que marca un nodo como visitado asume que ya encontró el camino óptimo. Un peso negativo posterior podría mejorar ese camino — algo que Dijkstra ignora.