19 - Caminos mínimos en grafos ponderados (Dijkstra)

En muchos problemas reales (rutas, redes, mapas, costos) cada arista tiene un peso distinto. Buscamos el camino de costo mínimo, no solo menos saltos. Con pesos no negativos, el algoritmo clásico es Dijkstra.

Simulador de camino mínimo en un grafo ponderado con Dijkstra

19.1 Idea general y cuándo usar Dijkstra

Problema: dado un grafo ponderado con pesos ≥ 0 y un origen s, hallar el costo mínimo desde s a todos los nodos.

• Ciudades unidas por rutas (peso = distancia).
• Routers conectados (peso = latencia).
• Tareas con dependencias (peso = tiempo de ejecución).

Dijkstra expande una frontera de nodos con distancia definitiva y relaja aristas hacia sus vecinos.

19.2 Conceptos clave del algoritmo

• dist[v]: mejor costo conocido desde s a v; inicia en infinito excepto dist[s]=0.
• visitado[v]: marca si la distancia ya es definitiva.
• padre[v]: anterior en el camino mínimo para reconstruir la ruta.

Relajación de v → u con peso w: si dist[v] + w < dist[u], entonces actualizar dist[u] y padre[u]=v.

19.3 Dijkstra paso a paso (versión simple, sin heap)

1. Inicializar dist[*]=INF, visitado[*]=0; dist[s]=0.
2. Repetir n veces: elegir el no visitado con dist mínima; si es -1 o infinito, terminar.
3. Marcarlo como visitado y relajar sus aristas.

Al final, dist[v] tiene el costo mínimo y padre[v] permite reconstruir el camino. Condición: todos los pesos deben ser ≥ 0; con negativos usar Bellman-Ford.

19.4 Usos típicos de Dijkstra

• GPS y mapas: peso = km o tiempo estimado.
• Redes de computadoras: peso = latencia; protocolos como OSPF lo usan.
• Logística: minimizar costo de envío entre depósito y cliente.
• Videojuegos / IA: peso = dificultad del terreno.
• Planificación de tareas: peso = tiempo; en DAG da el tiempo total mínimo respetando dependencias.

19.5 Implementación con listas de adyacencia (sin heap)

Usamos listas de adyacencia con pares (destino, peso) y selección lineal del mínimo.

#define MAX 10000
#define INF 1000000000

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

Edge *adj[MAX];

void addEdge(int a, int b, int w, int dirigido) {
    Edge *e1 = malloc(sizeof(Edge));
    e1->to = b; e1->w = w; e1->next = adj[a];
    adj[a] = e1;
    if (!dirigido) {
        Edge *e2 = malloc(sizeof(Edge));
        e2->to = a; e2->w = w; e2->next = adj[b];
        adj[b] = e2;
    }
}

19.6 Aplicación completa para probar en CLion

Programa completo: usa un grafo cargado en código (sin entrada por teclado), ejecuta Dijkstra desde un origen fijo, muestra distancias y reconstruye un camino.

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

#define INF 1000000000

typedef struct Edge {
  int to;
  int w;
  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 agregarAristaDirigida(Graph *g, int u, int v, int w) {
  Edge *e = malloc(sizeof(Edge));
  e->to = v;
  e->w = w;
  e->next = g->adj[u];
  g->adj[u] = e;
}

void dijkstra(const Graph *g, int origen, int *dist, int *padre) {
  int *visitado = calloc(g->n, sizeof(int));
  for (int i = 0; i < g->n; i++) {
    dist[i] = INF;
    padre[i] = -1;
  }
  dist[origen] = 0;

  for (int iter = 0; iter < g->n; iter++) {
    int v = -1;
    for (int i = 0; i < g->n; i++) {
      if (!visitado[i] && (v == -1 || dist[i] < dist[v])) v = i;
    }
    if (v == -1 || dist[v] == INF) break;
    visitado[v] = 1;
    for (Edge *e = g->adj[v]; e; e = e->next) {
      int u = e->to;
      int w = e->w;
      if (dist[v] + w < dist[u]) {
        dist[u] = dist[v] + w;
        padre[u] = v;
      }
    }
  }
  free(visitado);
}

void imprimirCamino(int origen, 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] == -1) break;
    v = padre[v];
  }
  printf("Camino minimo desde %d hasta %d: ", origen, destino);
  for (int i = tope - 1; i >= 0; i--) {
    printf("%d%s", pila[i], (i ? " -> " : "\n"));
  }
}

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

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

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

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

  printf("\n");
  imprimirCamino(origen, destino, padre);

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