Cómo funciona
Cada celda cuesta su peso al entrar en ella: aquí, la altura de la baldosa. Dijkstra
guarda en una frontera las celdas alcanzadas con el mejor coste g conocido y saca
siempre la de menor g. Como los pesos no son negativos, ninguna ruta posterior puede
abaratarla: su coste es definitivo y la celda se cierra.
Después relaja sus vecinos: si llegar a través de la celda cerrada es más barato que lo
que tenían, se actualizan su g y su padre. La frontera se dibuja como un estante ordenado: la celda de la
izquierda es la siguiente en salir.
Paso a paso: rodear una colina
Mapa de 7 × 5 de A3 a G3. En el centro hay una colina de 3 × 3 (de C2 a E4) con peso 5; el resto pesa 1.
- 01Cierro A3 (g = 0): A2, B3 y A4 entran en la frontera con g = 0 + 1 = 1.
- 02Las celdas se cierran en orden de g: primero las de 1, luego las de 2… Entrar en la colina cuesta 5, así que sus celdas reciben g altos y esperan en el estante mientras el llano se va cerrando.
- 03G3 sale con g = 10 rodeando la colina por arriba: A3 → A2 → A1 → B1 → … → G1 → G2 → G3. Se cierran 31 de las 35 celdas.
- ΣBFS, que no mira los pesos, iría recto por la colina: 6 pasos que cuestan 1 + 5 + 5 + 5 + 1 + 1 = 18. Dijkstra da 10 pasos pero paga 10.
Límites
Necesita pesos no negativos: con un peso negativo, una celda ya cerrada podría
abaratarse después (para eso existe Bellman-Ford). Y explora en todas las direcciones por igual, también
hacia donde no está el destino. A* añade una estimación de lo que falta para corregir eso.
Complejidad
- Con un montículo
- O((V + E) log V)
- Con un array
- O(V²)
- Memoria
- O(V)
- Óptimo
- Sí, pesos ≥ 0
- Estructura
- Cola de prioridad
- En una rejilla
- V celdas, E ≤ 4V