Edizione didattica italiana

Algoritmo di Dijkstra in C

Calcola distanze minime in un grafo con pesi non negativi.

Imposta a zero la distanza dalla sorgente e a infinito o sconosciuto le altre. Scegli il vertice non visitato con distanza minima e rilassa gli archi: aggiorna una distanza se passare da quel vertice la riduce.

Dijkstra richiede pesi non negativi. Distingui un arco assente da uno di peso zero secondo la rappresentazione. Non sommare un peso al valore usato per infinito e controlla gli overflow.

La versione con matrice e selezione lineare costa generalmente O(V²). Prova vertici irraggiungibili e percorsi alternativi. Per pesi negativi serve un altro algoritmo.

Codice sorgente

#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;
}

Apri nel compilatore

Risultato atteso

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

Domande frequenti

Perché il codice e alcuni risultati restano in inglese?

Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.