Algoritmo de Dijkstra — camino más corto paso a paso

El algoritmo de Dijkstra encuentra los caminos más cortos desde un nodo inicial en un grafo ponderado, siempre que todos los pesos de las aristas sean no negativos. Si solo te importa un destino, puedes detenerte en cuanto ese destino quede fijado.

La idea central es voraz: siempre se continúa desde el nodo no fijado con la menor distancia conocida. Eso solo funciona bajo la condición de pesos no negativos.

Qué resuelve el algoritmo de Dijkstra

Usa el algoritmo de Dijkstra cuando tienes un grafo con costos en las aristas y quieres la ruta más barata. El costo puede representar distancia, tiempo de viaje, energía u otra cantidad que quieras minimizar.

Funciona en grafos dirigidos o no dirigidos. La condición clave es explícita: cada peso de arista debe ser al menos $0$.

Cómo funciona el algoritmo

Cada nodo mantiene una distancia tentativa desde el nodo inicial. Al principio, el nodo inicial tiene distancia $0$ y todos los demás nodos tienen distancia $\infty$.

Luego repite este ciclo:

1. Elige el nodo no fijado con la menor distancia tentativa.
2. Revisa cada vecino a través de ese nodo.
3. Si la nueva ruta es más barata, actualiza la distancia del vecino.
4. Marca el nodo actual como fijado.

El paso 3 se llama relajación. Un nodo fijado ya está terminado: su distancia más corta es definitiva, siempre que el grafo no tenga aristas con peso negativo.

Algoritmo de Dijkstra paso a paso

Aquí está el procedimiento completo en forma compacta:

1. Elige un nodo inicial.
2. Asigna a su distancia el valor $0$ y a todas las demás distancias el valor $\infty$.
3. Selecciona el nodo no fijado con la menor distancia tentativa.
4. Relaja sus aristas salientes.
5. Marca ese nodo como fijado.
6. Repite hasta que todos los nodos alcanzables queden fijados, o detente cuando tu nodo objetivo quede fijado.

Si además guardas qué nodo anterior causó cada actualización, puedes recuperar el camino real, no solo la distancia final.

Ejemplo resuelto de camino más corto

Supón que el grafo tiene estos pesos de arista:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Queremos el camino más corto de $A$ a $D$.

Empieza con:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Fija primero $A$ y relaja sus aristas:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

La menor distancia no fijada ahora está en $C$, así que fija $C$ después.

Pasando por $C$:

• Pasando por $C$, el camino a $B$ cuesta $1+2=3$, que mejora el $4$, así que actualiza $\text{dist}(B)=3$.
• Pasando por $C$, el camino a $D$ cuesta $1+5=6$, así que asigna $\text{dist}(D)=6$.

Ahora $B$ tiene la menor distancia no fijada, así que fija $B$.

Pasando por $B$, el camino a $D$ cuesta:

$$3+1=4$$

Eso mejora el $6$, así que actualiza $\text{dist}(D)$ de $6$ a $4$.

Ahora $D$ es el nodo no fijado más pequeño. Fíjalo y detente.

El camino más corto es:

$$A \to C \to B \to D$$

con costo total:

$$1+2+1=4$$

Este ejemplo muestra el patrón clave: una ruta que al principio parecía peor, $A \to B$, después se volvió mejor a través de $C$. El algoritmo de Dijkstra permite eso mientras $B$ siga sin fijarse. Una vez que un nodo queda fijado, su distancia ya no cambia.

Por qué importan los pesos no negativos

Supón que el nodo no fijado más barato en este momento tiene distancia $d$. Cualquier nuevo camino hacia ese nodo que se descubra más tarde tendría que venir de otro nodo no fijado cuya distancia tentativa sea al menos $d$, y luego sumar una arista de peso al menos $0$.

Así que esa ruta posterior no puede mejorar a $d$. Por eso es seguro fijar la menor distancia tentativa cuando todos los pesos son no negativos.

Si existe una arista negativa, ese argumento deja de funcionar. Un camino que ahora parece caro puede volverse más barato después, lo que significa que fijar un nodo demasiado pronto puede dar una respuesta incorrecta.

Errores comunes con el algoritmo de Dijkstra

Usarlo con una arista negativa

Incluso una sola arista negativa puede romper la lógica voraz. Si pueden aparecer pesos negativos, usa otro método de camino más corto.

Tratar "visto" como "terminado"

Un nodo puede tener ya una distancia tentativa y aun así no estar terminado. Solo un nodo fijado tiene una distancia mínima definitiva.

Olvidar la tabla de nodos anteriores

Las distancias te dicen el costo. Si además quieres la ruta en sí, guarda qué nodo fue el último en mejorar cada distancia.

Dónde se usa el algoritmo de Dijkstra

El algoritmo de Dijkstra se usa cuando un problema puede modelarse como un recorrido por un grafo con costos no negativos:

• Planificación de rutas en mapas
• Enrutamiento de redes
• Movimiento de robots en cuadrículas ponderadas
• Búsqueda de caminos en videojuegos cuando los costos de movimiento varían

También es un ejemplo clásico de algoritmo voraz cuya corrección depende de una condición precisa.

Prueba un problema parecido

Dibuja un grafo con cinco nodos y pesos de arista positivos, y luego ejecuta el algoritmo de Dijkstra a mano con una tabla de distancias. Si quieres un buen siguiente paso, prueba tu propia versión en un grafo nuevo y comprueba exactamente cuándo cada nodo pasa a ser seguro de fijar.