16 · Distancias en grafos
Grafos y consultas · Ruta de Aprendizaje
Antes de empezar. Listas de adyacencia y BFS: 15 - Grafos I - BFS y DFS.
🎯 Objetivos
Al terminar este módulo sabes:
- Calcular distancias mínimas con BFS (y por qué funciona).
- Reconstruir el camino, no solo su largo.
- Distinguir cantidad de aristas de suma de pesos y reconocer cuándo usar Dijkstra.
📖 La lección
BFS mide distancias
Cuando cada arista cuesta 1 paso, el BFS visita los nodos por capas:
primero los que están a 1, luego a 2… Así, la primera vez que alcanzas un
nodo, llegaste por un camino mínimo. El arreglo dist[] hace de “visitado”
y de medida a la vez.
Usemos este grafo: n=5, origen=1 y aristas no dirigidas 1–2, 1–3, 3–4; el 5 está aislado. Reserva ady con n+1 posiciones e inserta cada arista en ambos sentidos.
Desde 1 alcanzamos 2 y 3 en un paso; desde 3, alcanzamos 4 en dos.
El 5 no se alcanza. Antes de programar ya sabemos que las distancias son
0,1,1,2,−1. El código conservará esa información en dist y recordará con
padre por dónde llegó a cada nodo.
// supone: int n, origen; vector<vector<int>> ady; // el grafo, leído como en el módulo 15
vector<int> dist(n + 1, -1), padre(n + 1, -1);
queue<int> q;
dist[origen] = 0;
q.push(origen);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : ady[u])
if (dist[v] == -1) { // primera vez que lo alcanzamos
dist[v] = dist[u] + 1; // por capas: esta ES la mínima
padre[v] = u; // recordar de dónde venimos
q.push(v);
}
}| Sale | Cola después | Nuevos dist / padre |
|---|---|---|
| 1 | 2,3 | dist[2]=1, padre[2]=1; dist[3]=1, padre[3]=1 |
| 2 | 3 | ninguno |
| 3 | 4 | dist[4]=2, padre[4]=3 |
| 4 | vacía | ninguno |
Al terminar, dist[1..5]={0,1,1,2,−1}. Para destino 4 se reconstruye 1,3,4; para 5 no existe camino. El siguiente dibujo muestra otro grafo para destacar sus capas.
Si al final dist[destino] == -1, no hay camino — respuesta válida también.
Si el diagrama no cabe, deslízalo horizontalmente.
Cada nodo recibe su dist la primera (y única) vez que lo alcanzan, y en ese
momento se anota quién lo alcanzó: ese es padre[], las aristas gruesas del
dibujo. Juntas forman un árbol con raíz en el origen, y el camino más
corto a cualquier nodo es su rama.
Reconstruir el camino
Muchos problemas piden el camino, no solo su longitud. Una distancia dice
cuántas aristas hay, pero no por dónde pasar. Al descubrir un vértice v
desde u, guardamos padre[v] = u: una conexión concreta que permite reconstruir
el recorrido. No es necesariamente el vecino con menor número.
Volvamos al ejemplo numérico de esta clase: desde 1 descubrimos 3, y desde
3 descubrimos 4. Por eso padre[4] = 3, padre[3] = 1 y padre[1] = -1.
Para llegar a 4 seguimos esos datos hacia atrás, hasta el origen:
Si el diagrama no cabe, deslízalo horizontalmente.
u actual | camino tras agregarlo | Siguiente: padre[u] |
|---|---|---|
| 4 | [4] | 3 |
| 3 | [4, 3] | 1 |
| 1 | [4, 3, 1] | −1: terminar |
El −1 es una señal de término y no se agrega al camino. Invertir la lista
produce [1,3,4]: tres vértices y dos aristas, de acuerdo con dist[4] = 2.
El código realiza exactamente esa caminata:
// supone: int destino; vector<int> padre, dist; // resultados del BFS anterior
vector<int> camino;
if (dist[destino] != -1) {
for (int u = destino; u != -1; u = padre[u]) camino.push_back(u);
reverse(camino.begin(), camino.end());
}Si dist[destino] == -1, el camino queda vacío: el destino es
inalcanzable. Si el destino es el origen, el resultado contiene solo ese
nodo y su distancia es cero. padre == -1 por sí solo no distingue esos casos.
Si hay dos caminos mínimos, el padre elegido al descubrir el nodo conserva
uno de ellos; esta reconstrucción no enumera todos. Seguir e invertir un
camino de k vértices cuesta O(k) tiempo y usa O(k) espacio para la respuesta.
BFS en grillas y multifuente
En una grilla de filas ..# y ..., desde la celda (0,1) podemos ir a
(0,0) y (1,1). La candidata (0,2) es un muro y (−1,1) queda fuera. Cada
movimiento permitido es una arista de costo 1: la misma cola sirve, guardando
pares (fila,columna) y una matriz de distancias. Primero comprueba límites,
después muros y por último si la celda ya se descubrió.
Dos aplicaciones del recorrido del módulo 15:
- Laberintos: BFS sobre celdas con los
dx/dyda la salida más corta — y a diferencia del DFS recursivo, la cola no revienta la pila en grillas de 1000×1000. - Multifuente: “¿a qué distancia está cada celda del incendio más cercano?” — encola todos los orígenes con distancia 0 antes de partir. Sale gratis con el mismo código.
En un camino 1–2–3–4–5, con orígenes 1 y 5, las distancias al más cercano son 0,1,2,1,0. Primero encolamos [1,5]; luego se descubren 2 y 4 a distancia 1; finalmente 3 a distancia 2. No hacemos un BFS completo por origen.
Esta inicialización reemplaza las líneas que ponen un solo origen en la cola. Después se ejecuta el mismo while de BFS:
// supone: int n; vector<int> origenes; // nodos válidos 1..n
vector<int> dist(n + 1, -1), padre(n + 1, -1);
queue<int> q;
for (int s : origenes) {
if (dist[s] != -1) continue; // no encolar un origen repetido
dist[s] = 0;
q.push(s);
}Si dos orígenes alcanzan un nodo a la misma distancia, cualquiera puede quedar como antecesor de su camino; la distancia mínima no cambia.
Si el diagrama no cabe, deslízalo horizontalmente.
Del camino de celdas a movimientos. En un laberinto, guarda al descubrir cada celda su celda anterior y el movimiento usado para llegar (D, U, R o L). Al reconstruir desde el destino, recoge esos movimientos y después invierte el string. Por ejemplo (0,0) → (0,1) → (1,1) produce RD; al retroceder se recoge primero D y luego R. Comprueba alcanzabilidad antes de reconstruir; si origen y destino coinciden, la secuencia de movimientos es vacía.
Cuando los pasos no valen lo mismo
Si las aristas tienen pesos distintos, BFS deja de dar la mínima (dos pasos baratos pueden valer menos que uno caro):
Si el diagrama no cabe, deslízalo horizontalmente.
El BFS sigue creyendo que “una arista = un paso”, y por eso se queda con el camino de 5. Si todos los pesos fueran iguales y positivos, minimizar pasos seguiría minimizando costo. Para pesos distintos no negativos, una opción es Dijkstra: la misma idea de expandir lo más cercano primero, pero con una cola de prioridad eligiendo siempre el nodo de menor distancia acumulada. En esta clase aprendemos a reconocer cuándo toca; su implementación te espera en la página del algoritmo y en el módulo 18.
🏋️ Práctica
Práctica directa: Distancia y camino
Grafo no dirigido con nodos 1..5 y aristas 1–2,1–3,3–4. Desde 1, responde distancia a 4 y un camino: 2 y 1 3 4. Para destino 5 responde SIN CAMINO.
Idea para comprobar tu solución
Las distancias por capas dan 0,1,1,2,−1. padre permite reconstruir; no intentes reconstruir el nodo aislado.
Variación: Empates y destinos imposibles
En un grafo no dirigido con vértices 0..4 y aristas 0–1, 0–2, 1–3 y 2–3, encuentra un camino mínimo de 0 a 3 y decide si existe uno de 0 a 4.
Una pista, si la necesitas
Puede haber más de un camino correcto de la misma longitud.
Contrastar el razonamiento
La distancia a 3 es 2: sirven 0–1–3 y 0–2–3. El padre guardado por BFS depende del orden de vecinos. El vértice 4 es inalcanzable: conserva la marca correspondiente y no reconstruyas un camino inexistente.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Risk | Nacional 2016 | BFS multifuente por capas (≤ K turnos) |
| 2 | Ajedrez | Nacional 2015 | BFS del caballo + casos cerrados por pieza |
| 3 | ⭐ La cueva de hielo | Clasificatoria 2016 | deslizamientos como aristas; BFS y su límite |
| 4 | ⭐⭐ Guerrera Dragona | Nacional 2024 | aristas de costo 0 y 1: la puerta a Dijkstra |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Shortest path of the king (3A) | ★★ (1000) | distancias en tablero, con movimientos de rey |
| 2 | Badge (1020B) | ★★ (1000) | seguir sucesores hasta repetir |
| 3 | Message Route (CSES 1667) | ★★★ (—) | BFS + reconstruir el camino con padre[] |
| 4 | ⭐ Labyrinth (CSES 1193) | ★★★★ (—) | BFS en grilla + camino como string |
| 5 | ⭐⭐ Dijkstra? (20C) | ★★★★★ (1900) | opcional para valientes: tu primer Dijkstra de verdad |
Para pensar: menos aristas no siempre es menos distancia
En un grafo dirigido hay aristas A → B de costo 10, A → C de costo 1
y C → B de costo 1. ¿Qué camino a B encuentra un BFS desde A?
¿Es el de menor costo?
Ver razonamiento
BFS descubre B directamente desde A, a una arista de distancia. El camino
A → C → Btiene dos aristas, pero cuesta 2 frente a 10 del directo. Las capas de BFS ordenan por cantidad de aristas, no por suma de pesos. Si todas las aristas cuestan lo mismo y ese costo es positivo, ambos objetivos coinciden. Con costos no negativos distintos, Dijkstra ordena la exploración por la distancia acumulada.
← 15 - Grafos I - BFS y DFS · Ruta de Aprendizaje · 17 - Sumas de prefijos →