Edição didática em português. O código e suas saídas preservam o original.

Algoritmo de Dijkstra em C

Calcule distâncias mínimas a partir de uma origem em um grafo com pesos não negativos.

Inicialize a distância da origem em zero e as demais como desconhecidas ou infinitas. Escolha o vértice não visitado de menor distância e relaxe suas arestas: se passar por ele melhorar uma distância, atualize-a.

Dijkstra exige pesos não negativos. Diferencie ausência de aresta de uma aresta com peso zero conforme a representação utilizada. Não some um peso a um valor que representa infinito e verifique estouros ao ampliar a faixa.

A versão com matriz e seleção linear costuma custar O(V²). Teste vértices desconectados e caminhos alternativos; um vértice inalcançável deve continuar identificado como tal. Para pesos negativos, é necessário outro 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 no compilador

Saída esperada

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

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.