Dijkstra: shortest path con costos heterogéneos
Agrega obstaculos en tu calculo de rutas. Óptimo en costos, no solo en pasos.
Publicado: · Por Juanjo "Banyo" López
0. Introducción
BFS encuentra el camino más corto en número de pasos. Eso funciona si todos los pasos cuestan lo mismo. En cuanto un terreno cuesta más que otro — barro contra camino, escalera contra cuesta, el río de Diablo II — BFS te miente y Dijkstra entra a escena.
Dijkstra es exactamente la misma idea que BFS, con un cambio: en vez de una cola FIFO, usa una priority queue. La PQ siempre te entrega el nodo con menor costo acumulado, no el que se encoló primero. Esa única diferencia convierte “lo más cercano en pasos” en “lo más barato en costos”.
¿Cuándo usarlo?
- Tu mundo tiene terrenos con costos distintos (barro, agua, escalera, suelo normal).
- Buscas el camino óptimo en costo total, no en pasos.
- No tienes un goal único — quieres el costo desde el origen a todos los nodos (Dijkstra te lo da gratis: es un single-source shortest path, no solo one-to-one).
- Vas a usar el resultado para construir un flow field, un Dijkstra map (estilo Brogue), o un heat map de peligro.
¿Cuándo NO?
- Todos los pasos cuestan lo mismo: usa BFS, es más simple.
- Hay costos negativos: Dijkstra falla — necesitas Bellman-Ford. (Spoiler: en juegos casi nunca hay costos negativos. Pasos hacia atrás en el tiempo son raros.)
- El mapa es enorme y tienes un goal específico: A* explora 5-10× menos. Dijkstra solo gana si necesitas multi-goal o si el goal cambia mucho.
1. La idea: BFS con prioridad por costo
Pinta terrenos con el selector. Shift+click mueve el origen, Alt+click mueve el destino. La frontera de Dijkstra se colorea por costo acumulado: cuesta más cruzar barro o pantano, así que el camino verde rodea las zonas oscuras.
Figura 1 — Pinta terrenos con el selector. Verde es barato (1), pantano oscuro es caro (10). El frente de Dijkstra se colorea por costo acumulado y el camino verde rodea las zonas oscuras cuando el desvío sale más barato que cruzar.
1.1 ¿Qué cambia respecto a BFS?
Compara las dos “cabezas” del bucle:
BFS:
while queue not empty
current = queue.dequeue() # FIFO: el más antiguo
Dijkstra:
while pqueue not empty
current = pqueue.popMin() # min-heap: el de MENOR costo acumulado
Y el bookkeeping cambia: en BFS basta con un Set visited. En Dijkstra necesitas un gScore (el menor costo conocido para llegar a cada nodo) que se va relajando:
function dijkstra(grid, start, goal)
gScore = Map.fillWith(Infinity)
gScore[start] = 0
parent = Map()
pq = MinPriorityQueue()
pq.push(start, priority = 0)
while pq not empty
current = pq.popMin()
if current == goal: return reconstructPath(parent, goal)
for each neighbor of current
tentative = gScore[current] + cost(neighbor)
if tentative < gScore[neighbor]
gScore[neighbor] = tentative
parent[neighbor] = current
pq.push(neighbor, priority = tentative)
Tres puntos clave:
tentative < gScore[neighbor]es la “relajación”: solo actualizamos si encontramos un camino más barato al vecino. Esa es la garantía de óptimo.- Reinsertar en la PQ está bien; el nodo viejo (con prioridad mayor) saldrá después y se ignorará porque ya tendrá
gScoremejor. - Costo de entrar a una celda, no de “moverse hacia ella”: el costo se asocia a la celda destino. Da igual la celda de origen.
1.2 La garantía de óptimo
Cuando Dijkstra extrae un nodo de la PQ, su gScore es definitivo. Nunca encontrarás un camino más barato a ese nodo: cualquier otro camino debe pasar por nodos con gScore mayor (que aún están en la PQ con prioridad mayor). Esa propiedad es lo que hace Dijkstra correcto, y por la misma razón no funciona con costos negativos: la asunción se rompe.
2. Dijkstra vs BFS — la prueba visual
El río marrón cuesta 8 por celda. BFS lo cruza en línea recta porque cuenta pasos, no costo. Dijkstra rodea — el desvío suma menos. Mira los costos al final: en mapas con costos heterogéneos, BFS te miente.
Figura 2 — Mismo origen y goal. El río marrón cuesta 8 por celda. BFS lo cruza recto (cuenta pasos, no costos); Dijkstra lo rodea (suma costos). El número que aparece debajo de cada panel es el costo real del camino encontrado.
Si BFS reporta más costo que Dijkstra, BFS encontró un camino válido pero no óptimo. Esa diferencia es el “precio del costo uniforme”.
2.1 La priority queue, sin magia
Dijkstra depende de una estructura que entrega siempre el mínimo. La implementación canónica es un min-heap binario, con operaciones O(log n):
Una priority queue (min-heap) entrega siempre el elemento de menor prioridad. Es lo que hace Dijkstra eficiente: en vez de buscar linealmente el menor costo, lo extrae en O(log n). Pulsa push/pop o deja el auto-modo.
Figura 3 — El min-heap como árbol binario: el padre siempre tiene prioridad ≤ que sus hijos. Pulsa push/pop o deja el auto-modo. La raíz (verde) es el siguiente que saldrá.
Implementación de bolsillo:
class MinHeap
data: List<{priority, value}>
push(p, v)
data.append({p, v})
bubbleUp(data.length - 1)
popMin() -> v
top = data[0]
last = data.pop()
if data not empty
data[0] = last
sinkDown(0)
return top.value
Bubble-up y sink-down son los movimientos típicos: la operación de inserción sube el nuevo nodo hasta su lugar; pop reemplaza la raíz con el último y baja la raíz nueva hasta cumplir la propiedad de heap.
3. Dijkstra map — un solo origen, todos los destinos
Una propiedad de Dijkstra que A* pierde: si lo dejas correr sin goal, te calcula el costo desde el origen a cada celda del mapa. Eso te da una herramienta poderosa: el Dijkstra map.
function dijkstraMap(grid, source) -> Float[][]
// ejecuta Dijkstra ignorando "goal", visita todo lo alcanzable
return gScore // mapa de costos a TODA celda
¿Para qué sirve?
- Huida por gradiente: enemigos de un roguelike huyen del jugador siguiendo el gradiente decreciente del mapa. Sin pathfinding por agente. Lo verás en Dijkstra aplicado (tanda 6).
- Distance maps para IA: ¿cuán lejos está cada celda del jugador? Útil para decisiones tácticas.
- Influence maps combinados: varios Dijkstra maps superpuestos forman zonas de control (un equipo influye desde sus unidades, otro desde las suyas; la diferencia te dice quién domina cada celda).
- Flow fields: un Dijkstra map desde el goal + dirección hacia el vecino con menor distancia = un flow field para multitudes (tanda dedicada en flow-fields).
4. Pseudocódigo completo
function dijkstra(grid, start, goal)
gScore = Map.fillWith(Infinity)
gScore[start] = 0
parent = Map()
pq = MinPriorityQueue()
pq.push(start, 0)
while pq not empty
current = pq.popMin()
if current == goal:
return reconstructPath(parent, goal)
for each neighbor of walkableNeighbors(current)
stepCost = cost(neighbor) # costo de ENTRAR a neighbor
tentative = gScore[current] + stepCost
if tentative < gScore[neighbor]
gScore[neighbor] = tentative
parent[neighbor] = current
pq.push(neighbor, tentative)
return null # no hay camino
function reconstructPath(parent, goal)
path = [goal]
while parent[goal] exists
goal = parent[goal]
path.append(goal)
return reverse(path)
5. Implementación en Unity / C#
Snippet representativo. El asset trae la versión optimizada (índices planos, Stack<int> para pool de nodos cerrados, comparador especializado).
using System.Collections.Generic;
using UnityEngine;
public class PathfindingGrid {
public int Cols, Rows;
public bool[] Walkable; // length Cols * Rows
public float[] Cost; // length Cols * Rows
public int Idx(int x, int y) => y * Cols + x;
}
public static class Dijkstra {
static readonly Vector2Int[] Dirs4 = {
new(1, 0), new(-1, 0), new(0, 1), new(0, -1),
};
public static List<Vector2Int> Find(PathfindingGrid g, Vector2Int start, Vector2Int goal) {
int n = g.Cols * g.Rows;
var gScore = new float[n];
var parent = new int[n];
for (int i = 0; i < n; i++) { gScore[i] = float.PositiveInfinity; parent[i] = -1; }
var startIdx = g.Idx(start.x, start.y);
gScore[startIdx] = 0;
// SortedSet = tree-based priority queue. En .NET 6+ usa PriorityQueue.
var pq = new SortedSet<(float p, int idx)>();
pq.Add((0, startIdx));
while (pq.Count > 0) {
var top = pq.Min;
pq.Remove(top);
int cur = top.idx;
int cx = cur % g.Cols, cy = cur / g.Cols;
if (cx == goal.x && cy == goal.y) return Reconstruct(parent, g.Cols, goal);
foreach (var d in Dirs4) {
int nx = cx + d.x, ny = cy + d.y;
if (nx < 0 || ny < 0 || nx >= g.Cols || ny >= g.Rows) continue;
int ni = g.Idx(nx, ny);
if (!g.Walkable[ni]) continue;
float tentative = gScore[cur] + g.Cost[ni];
if (tentative < gScore[ni]) {
if (gScore[ni] != float.PositiveInfinity) pq.Remove((gScore[ni], ni));
gScore[ni] = tentative;
parent[ni] = cur;
pq.Add((tentative, ni));
}
}
}
return null;
}
static List<Vector2Int> Reconstruct(int[] parent, int cols, Vector2Int goal) {
var path = new List<Vector2Int>();
int cur = goal.y * cols + goal.x;
while (cur != -1) {
path.Add(new Vector2Int(cur % cols, cur / cols));
cur = parent[cur];
}
path.Reverse();
return path;
}
}
6. En otros engines
- Godot:
AStarGrid2DyAStar2D— su nombre dice “A*” pero si pasas heurística cero, son Dijkstra. Para Dijkstra map (multi-target), tienes que iterar manualmente. - Unreal: la
FNavigationSystemse ocupa del NavMesh; para Dijkstra sobre grid de gameplay, lo escribes a mano. La PriorityQueue de la stdlib (TArray+ funcionesHeapPush/HeapPop) sirve. - JavaScript / TypeScript: la lib del sitio (
~/lib/viz/sim/pathfinding) implementadijkstra()como generador para que las visualizaciones puedan animarlo paso a paso.
7. Quiz
Pon a prueba lo que entendiste
Responde una por una. La explicación aparece al elegir, correcta o no.
Tu mapa tiene barro (costo 5), agua (costo 10) y suelo normal (costo 1). Necesitas el camino óptimo. ¿BFS o Dijkstra?
Estás implementando Dijkstra y notas que cada extracción del 'mínimo' hace un sort completo del array. ¿Qué estás pagando?
Tienes un goal específico y un mapa de 200x200. ¿Por qué A* sería mejor que Dijkstra acá?
Quieres que los enemigos huyan del jugador siguiendo el gradiente. ¿Qué estructura te conviene?
¿Por qué Dijkstra falla con costos negativos?