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);
        }
}
SaleCola despuésNuevos dist / padre
12,3dist[2]=1, padre[2]=1; dist[3]=1, padre[3]=1
23ninguno
34dist[4]=2, padre[4]=3
4vacíaninguno

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.

sdist 0adist 1bdist 1cdist 2ddist 2edist 2fdist 3capa 0capa 1capa 2capa 3camino a f:f ← d ← a ← sleyendo padre[]y dándolo vuelta

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:

Desde el destino, seguimos padre[]431padre[4]padre[3]padre[1] = −1: termina; −1 no es un nodo.guardamos [4, 3, 1]invertircamino: [1, 3, 4]3 vértices, 2 aristas: distancia 2.

Si el diagrama no cabe, deslízalo horizontalmente.

u actualcamino tras agregarloSiguiente: 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/dy da 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.

2123441🔥123321232132321🔥4344321todos los focos entran a la colacon distancia 0 antes de partirel BFS avanza por capas desdetodos a la vez: cada celda recibela distancia al foco más cercanomismo código, misma O(n·m)el número es la distancia al 🔥 más cercano

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):

511satBFS elige s→t: una aristapero cuesta 5lo barato es s→a→tdos aristas, costo 2BFS minimiza aristas; Dijkstra admite pesos no negativos

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.

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.

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):

#ProblemaFaseQué practica
1RiskNacional 2016BFS multifuente por capas (≤ K turnos)
2AjedrezNacional 2015BFS del caballo + casos cerrados por pieza
3⭐ La cueva de hieloClasificatoria 2016deslizamientos como aristas; BFS y su límite
4⭐⭐ Guerrera DragonaNacional 2024aristas de costo 0 y 1: la puerta a Dijkstra

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Shortest path of the king (3A)★★ (1000)distancias en tablero, con movimientos de rey
2Badge (1020B)★★ (1000)seguir sucesores hasta repetir
3Message 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?


← 15 - Grafos I - BFS y DFS · Ruta de Aprendizaje · 17 - Sumas de prefijos →