Dijkstra en C: ejercicio resuelto

Si buscas Dijkstra en C ejercicio resuelto, aquí tienes la implementación clásica con matriz de adyacencia: encuentra el camino más corto desde un nodo origen hasta todos los demás nodos de un grafo dirigido y ponderado con pesos no negativos.

La implementación con matriz es O(V²), adecuada para grafos densos o pequeños. Para grafos dispersos grandes se usa una cola de prioridad (min-heap), que da O((V + E) log V).

Enunciado

Dado un grafo de 5 nodos (0–4) con las siguientes aristas:

1
2
3
4
5
0→1 peso 10   0→3 peso 5
1→2 peso 1    1→3 peso 2
3→1 peso 3    3→2 peso 9   3→4 peso 2
4→2 peso 6    4→0 peso 7
2→4 peso 4

Encuentra las distancias mínimas desde el nodo 0 a todos los demás usando Dijkstra.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <limits.h>

#define V 5
#define INF INT_MAX

int grafo[V][V] = {
    {0,  10, 0,  5,  0},
    {0,  0,  1,  2,  0},
    {0,  0,  0,  0,  4},
    {0,  3,  9,  0,  2},
    {7,  0,  6,  0,  0}
};

int minimo_no_visitado(const int dist[], const int visitado[]) {
    int min = INF, idx = -1;
    for (int v = 0; v < V; v++) {
        if (!visitado[v] && dist[v] < min) {
            min = dist[v];
            idx = v;
        }
    }
    return idx;
}

void dijkstra(int origen) {
    int dist[V], visitado[V] = {0};

    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[origen] = 0;

    for (int iter = 0; iter < V - 1; iter++) {
        int u = minimo_no_visitado(dist, visitado);
        if (u == -1) break;
        visitado[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!visitado[v] && grafo[u][v] &&
                dist[u] != INF &&
                dist[u] + grafo[u][v] < dist[v]) {
                dist[v] = dist[u] + grafo[u][v];
            }
        }
    }

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

int main(void) {
    dijkstra(0);
    return 0;
}

Resultado esperado

1
2
3
4
5
6
Distancias desde nodo 0:
  0 → 0 : 0
  0 → 1 : 8
  0 → 2 : 9
  0 → 3 : 5
  0 → 4 : 7

Errores frecuentes

Usar pesos negativos: Dijkstra no funciona correctamente con aristas de peso negativo. Para ese caso se usa el algoritmo de Bellman-Ford.
No inicializar todas las distancias a INF antes de empezar: distancias sin inicializar producen caminos incorrectos.
Sumar INF + peso sin comprobar que dist[u] != INF: produce desbordamiento de entero.
Confundir grafos dirigidos con no dirigidos en la matriz: si el grafo es no dirigido, grafo[u][v] == grafo[v][u].

Aplicación práctica

Dijkstra es el algoritmo estándar para navegación GPS, enrutamiento de redes (OSPF), juegos de estrategia (búsqueda de caminos en mapas) y cualquier problema de camino mínimo con pesos no negativos. La versión con cola de prioridad es la que se usa en producción para grafos grandes.

Siguiente ejercicio recomendado

Práctica guiada y libro completo

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Por qué Dijkstra no funciona con pesos negativos?

Porque el algoritmo asume que una vez que un nodo se marca como visitado, su distancia ya es la mínima posible. Con pesos negativos podría existir un camino más corto que llegue a ese nodo más tarde, violando esa suposición. Bellman-Ford maneja pesos negativos en O(V·E).

¿Cuándo usar la versión con cola de prioridad frente a la de matriz?

La versión con cola de prioridad (min-heap) es O((V + E) log V) y se prefiere para grafos dispersos donde E « V². La versión con matriz es O(V²) y es más sencilla de implementar; es aceptable cuando V es pequeño (< 1000) o el grafo es denso.

¿Cómo reconstruir el camino, no solo la distancia?

Se añade un array predecesor[V] inicializado a -1. Cuando se relaja una arista y se actualiza dist[v], se guarda predecesor[v] = u. Al final, se recorre el array de predecesores desde el destino hasta el origen para obtener la ruta.