Skip to content
Snippets Groups Projects

Dijkstra's Algorithmus

  • Clone with SSH
  • Clone with HTTPS
  • Embed
  • Share
    The snippet can be accessed without any authentication.
    Authored by Bökelmann, Stephan
    dijkstra.c 2.79 KiB
    #include <stdio.h>
    #include <limits.h>
    
    #define V 9  // Anzahl der Knoten im Graphen
    
    /**
     * @brief Findet den Knoten mit dem minimalen Abstandswert, von den Knoten, die noch nicht im kürzesten Pfadbaum enthalten sind.
     * 
     * @param dist Array der kürzesten Distanzen von der Quelle zu jedem Knoten.
     * @param sptSet Array der Knoten, die im kürzesten Pfadbaum enthalten sind.
     * @return Index des Knotens mit dem minimalen Abstandswert.
     */
    int minDistance(int dist[], int sptSet[]) {
        int min = INT_MAX, min_index;
    
        for (int v = 0; v < V; v++)
            if (sptSet[v] == 0 && dist[v] <= min)
                min = dist[v], min_index = v;
    
        return min_index;
    }
    
    /**
     * @brief Druckt das Array der kürzesten Distanzen.
     * 
     * @param dist Array der kürzesten Distanzen von der Quelle zu jedem Knoten.
     */
    void printSolution(int dist[]) {
        printf("Knoten \t Abstand von der Quelle\n");
        for (int i = 0; i < V; i++)
            printf("%d \t %d\n", i, dist[i]);
    }
    
    /**
     * @brief Implementiert Dijkstra's Algorithmus für einen Graphen, der durch eine Adjazenzmatrix dargestellt wird.
     * 
     * @param graph Adjazenzmatrix des Graphen.
     * @param src Startknoten.
     */
    void dijkstra(int graph[V][V], int src) {
        int dist[V];  // Array zur Speicherung der kürzesten Distanzen von src zu i
        int sptSet[V]; // sptSet[i] wird wahr, wenn Knoten i im kürzesten Pfadbaum enthalten ist
    
        // Initialisiere alle Distanzen als unendlich und sptSet als falsch
        for (int i = 0; i < V; i++)
            dist[i] = INT_MAX, sptSet[i] = 0;
    
        // Abstand von der Quelle zu sich selbst ist immer 0
        dist[src] = 0;
    
        // Finde den kürzesten Pfad für alle Knoten
        for (int count = 0; count < V - 1; count++) {
            // Wähle den Knoten mit der minimalen Distanz, der noch nicht verarbeitet wurde
            int u = minDistance(dist, sptSet);
    
            // Markiere den ausgewählten Knoten als verarbeitet
            sptSet[u] = 1;
    
            // Aktualisiere den Abstandswert der benachbarten Knoten des ausgewählten Knotens
            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];
        }
    
        // Drucke das Array der kürzesten Distanzen
        printSolution(dist);
    }
    
    int main() {
        // Beispielgraph als Adjazenzmatrix
        int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                           {4, 0, 8, 0, 0, 0, 0, 11, 0},
                           {0, 8, 0, 7, 0, 4, 0, 0, 2},
                           {0, 0, 7, 0, 9, 14, 0, 0, 0},
                           {0, 0, 0, 9, 0, 10, 0, 0, 0},
                           {0, 0, 4, 14, 10, 0, 2, 0, 0},
                           {0, 0, 0, 0, 0, 2, 0, 1, 6},
                           {8, 11, 0, 0, 0, 0, 1, 0, 7},
                           {0, 0, 2, 0, 0, 0, 6, 7, 0}};
    
        dijkstra(graph, 0);
    
        return 0;
    }
    0% Loading or .
    You are about to add 0 people to the discussion. Proceed with caution.
    Finish editing this message first!
    Please register or to comment