Algoritmo de Dijkstra
Encuentra el camino más barato de un inicio a una meta. Siempre toma el lugar más barato que espera en una cola de prioridad, así que los costes se extienden desde el inicio como una inundación.
- tiempo O((V + E) log V)
- espacio O(V)
- usa una cola de prioridad
¿Qué significan estos términos?
- Coste: lo que cuesta un movimiento. En el laberinto, pisar suelo cuesta 1, barro 3 y agua 9; en el grafo, el número de la arista.
- Cola de prioridad: una cola donde pasa primero el más barato, no el que llegó antes.
- Estimación (h): una suposición del coste que falta. A* solo es exacto si nunca se pasa.
- Relajar una arista: comprobar si pasar por el lugar actual da a un vecino un coste menor y, si es así, quedárselo.
- en la cola
- actual
- listo
- camino más barato
- suelo · 1
- barro · 3
- agua · 9
- pared
Nuevo: Inicio en A1 con coste 0. Es lo único que hay en la cola.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige el pantano. El camino más barato rodea todo el barro: el doble de movimientos que la línea recta y, aun así, más barato (34 frente a 36).
Cómo funciona
Cada lugar recibe un coste: 0 el inicio, infinito el resto. Dijkstra guarda los lugares alcanzados en una cola de prioridad y siempre toma el más barato. Ese coste ya es definitivo, porque cualquier otro camino tendría que pasar por algo al menos igual de caro. Después mira cada vecino: si pasar por el lugar que acaba de tomar es más barato que el coste actual del vecino, el vecino recibe el nuevo coste y recuerda de dónde viene. Cuando toma la meta, esos enlaces llevan de vuelta por el camino más barato.
Cuándo es una buena opción
Usa Dijkstra cuando los movimientos cuestan distinto y ninguno cuesta menos de cero: mapas de carreteras y navegadores, enrutamiento de redes, la combinación de vuelos más barata. Si todo movimiento cuesta lo mismo, BFS da la misma respuesta de forma más sencilla. Con costes negativos Dijkstra puede fallar; para eso está Bellman-Ford.