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