18 - Caminos mínimos en grafos no ponderados

En un grafo no ponderado todas las aristas cuestan lo mismo: un paso. El camino mínimo entre dos vértices es el que usa la menor cantidad de aristas. Para este caso, el algoritmo ideal es la BFS (Breadth-First Search).

Simulador de camino mínimo en un grafo

18.1 BFS como Dijkstra sin peso

Cuando todos los pesos valen 1, no hace falta Dijkstra: BFS recorre por niveles y alcanza primero las distancias mínimas (Dijkstra se verá más adelante para grafos ponderados).

• Visita todos los vértices a distancia 1, luego a distancia 2, y así sucesivamente.
• La primera vez que llega a un nodo es por el camino más corto (en aristas).

Ejemplo: grafo A → B → C → D. Niveles: A (0), B (1), C (2), D (3). Distancia mínima A-D = 3 aristas. Camino: A → B → C → D.

18.2 Distancias mínimas

Se usa un arreglo dist[] inicializado en -1 y dist[origen] = 0. Al descubrir un vecino v desde u:

dist[v] = dist[u] + 1

Así se generan automáticamente las distancias en saltos.

18.3 Reconstrucción del camino

Para obtener el camino exacto se guarda padre[] (o prev[]): al descubrir v desde u, asignamos padre[v] = u. Luego:

camino = []
v = destino
mientras v != -1:
    camino.push(v)
    v = padre[v]
invertir(camino)

Ejemplo: padre[D]=C, padre[C]=B, padre[B]=A, padre[A]=-1. Camino reconstruido: A → B → C → D.

18.4 Casos típicos

• Laberintos en grillas: cada casilla vale un movimiento; BFS encuentra la salida más corta. Probar demo
• Redes sociales: distancia mínima entre personas (grado de separación). Probar demo
• Juegos tipo Pac-Man sin pesos: cuando todas las celdas libres valen 1 movimiento, BFS permite que enemigos encuentren rutas cortas. Probar demo
• Movimientos de piezas de ajedrez: hallar el camino mínimo (por ejemplo un caballo) desde una casilla de origen hasta otra. Probar demo
• Transporte sin pesos: mínimo de estaciones, transbordos o calles.
• Redes de routers uniformes: cantidad de saltos entre nodos.

18.5 Algoritmo de caminos mínimos en grafos no ponderados (CLion)

Implementación de BFS con distancias y reconstrucción del camino usando padre[], con un grafo cargado en código (sin entrada por teclado).

#include <stdio.h>
#include <stdlib.h>

typedef struct Edge {
  int to;
  struct Edge *next;
} Edge;

typedef struct {
  int n;
  Edge **adj;
} Graph;

Graph crearGrafo(int n) {
  Graph g;
  g.n = n;
  g.adj = calloc(n, sizeof(Edge *));
  return g;
}

void agregarAristaNoDirigida(Graph *g, int u, int v) {
  Edge *a = malloc(sizeof(Edge));
  a->to = v;
  a->next = g->adj[u];
  g->adj[u] = a;

  Edge *b = malloc(sizeof(Edge));
  b->to = u;
  b->next = g->adj[v];
  g->adj[v] = b;
}

void bfsDistancias(const Graph *g, int origen, int *dist, int *padre) {
  int *cola = malloc(g->n * sizeof(int));
  int ini = 0, fin = 0;
  for (int i = 0; i < g->n; i++) {
    dist[i] = -1;
    padre[i] = -1;
  }
  dist[origen] = 0;
  padre[origen] = origen;
  cola[fin++] = origen;

  while (ini < fin) {
    int u = cola[ini++];
    for (Edge *e = g->adj[u]; e; e = e->next) {
      int v = e->to;
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        padre[v] = u;
        cola[fin++] = v;
      }
    }
  }
  free(cola);
}

void imprimirCamino(int destino, const int *padre) {
  int pila[128];
  int tope = 0;
  int v = destino;
  while (v != -1 && tope < 128) {
    pila[tope++] = v;
    if (padre[v] == v) break;
    v = padre[v];
  }
  for (int i = tope - 1; i >= 0; i--) {
    printf("%d%s", pila[i], (i == 0) ? "\n" : " -> ");
  }
}

int main(void) {
  Graph g = crearGrafo(6);
  agregarAristaNoDirigida(&g, 0, 1);
  agregarAristaNoDirigida(&g, 0, 2);
  agregarAristaNoDirigida(&g, 1, 3);
  agregarAristaNoDirigida(&g, 1, 4);
  agregarAristaNoDirigida(&g, 2, 5);

  int origen = 0, destino = 5;
  int *dist = malloc(g.n * sizeof(int));
  int *padre = malloc(g.n * sizeof(int));

  bfsDistancias(&g, origen, dist, padre);

  printf("Distancias minimas desde %d:\n", origen);
  for (int i = 0; i < g.n; i++) {
    printf("Nodo %d: %d\n", i, dist[i]);
  }

  printf("\nCamino minimo de %d a %d: ", origen, destino);
  if (dist[destino] == -1) {
    printf("no existe\n");
  } else {
    imprimirCamino(destino, padre);
  }

  free(dist);
  free(padre);
  free(g.adj);
  return 0;
}