Nederlandse leereditie

Het algoritme van Dijkstra in C

Bereken kortste afstanden in een graaf met niet-negatieve gewichten.

Stel de bronafstand op nul en andere afstanden op oneindig of onbekend. Kies de onbezochte knoop met de kleinste afstand en ontspan de kanten: werk een afstand bij als de route via die knoop korter is.

Dijkstra vereist niet-negatieve gewichten. Onderscheid een ontbrekende kant van een kant met gewicht nul volgens de gekozen voorstelling. Tel geen gewicht op bij de oneindigheidswaarde en let op overloop.

De versie met matrix en lineaire selectie kost doorgaans O(V²). Test onbereikbare knopen en alternatieve routes. Negatieve gewichten vereisen een ander algoritme.

Broncode

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

Openen in de compiler

Verwacht resultaat

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

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.