Deutsche Lernausgabe

Dijkstras Algorithmus in C

Berechnen Sie kürzeste Entfernungen von einem Startknoten in Graphen mit nichtnegativen Gewichten.

Setzen Sie die Startentfernung auf null, die anderen auf unbekannt oder unendlich. Wählen Sie den unbesuchten Knoten mit kleinster Entfernung und relaxieren Sie seine Kanten: Verbessert ein Weg über ihn eine Entfernung, aktualisieren Sie diese.

Dijkstra setzt nichtnegative Gewichte voraus. Unterscheiden Sie je nach Darstellung eine fehlende Kante von einer Kante mit Gewicht null. Addieren Sie kein Gewicht zum Unendlichkeitswert und achten Sie auf Überläufe.

Die Variante mit Matrix und linearer Auswahl benötigt meist O(V²). Testen Sie unerreichbare Knoten und alternative Wege. Negative Gewichte erfordern einen anderen Algorithmus.

Quellcode

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

Im Compiler öffnen

Erwartetes Ergebnis

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

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.