Edición didáctica en español. El código y sus salidas conservan el original.

Algoritmo de Dijkstra en C

Calcula distancias mínimas desde un origen en un grafo con pesos no negativos.

Inicializa la distancia del origen en cero y las demás como desconocidas o infinitas. Elige el vértice no visitado de menor distancia y relaja sus aristas: si pasar por él mejora una distancia, actualízala.

Dijkstra requiere pesos no negativos. Distingue la ausencia de una arista de una arista de peso cero según la representación usada. No sumes un peso a un valor que representa infinito, y comprueba desbordamientos al ampliar el rango.

La versión con matriz y selección lineal suele costar O(V²). Prueba vértices desconectados y caminos alternativos; un vértice inalcanzable debe seguir identificado como tal. Para pesos negativos necesitas otro algoritmo.

Código C

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define V 5

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex 	 Distance from Source (%d)\n", src);
    for (int i = 0; i < V; i++) printf("%d 		 %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 8, 0},
        {4, 0, 8, 11, 0},
        {0, 8, 0, 7, 2},
        {8, 11, 7, 0, 9},
        {0, 0, 2, 9, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Abrir en el compilador

Salida esperada

Vertex 	 Distance from Source (0)
0 		 0
1 		 4
2 		 12
3 		 8
4 		 14

Preguntas frecuentes

¿Por qué el código y la salida siguen en inglés?

Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.