DijkstrasAlgorithm.h
/** * ***************************************************************************** * @file DijkstrasAlgorithm.h * @brief Dijkstra's Algorithm in C 迪杰斯特拉算法 最短路径算法 https://www.programiz.com/dsa/dijkstra-algorithm#google_vignette * IDE: VSCODE C11 * @author (geovindu,Geovin Du,涂聚文) * @date 2023-09-26 * @copyright geovindu * ***************************************************************************** */ #ifndef DIJKSTRASALGORITHM_H #define DIJKSTRASALGORITHM_H #include <stdio.h> #define INFINITY 9999 #define MAX 10 /** * @brief Dijkstra's Algorithm * * @param Graph * @param n * @param start */ void Dijkstra(int Graph[MAX][MAX], int n, int start); #endif
DijkstrasAlgorithm.c
/** * ***************************************************************************** * @file DijkstrasAlgorithm.c * @brief Dijkstra's Algorithm in C 迪杰斯特拉算法 最短路径算法 * IDE: VSCODE C11 https://www.programiz.com/dsa/dijkstra-algorithm#google_vignette * @author (geovindu,Geovin Du,涂聚文) * @date 2023-09-26 * @copyright geovindu * ***************************************************************************** */ #include <stdio.h> #include "include/DijkstrasAlgorithm.h" /** * @brief * * @param Graph * @param n * @param start */ void Dijkstra(int Graph[MAX][MAX], int n, int start) { int cost[MAX][MAX], distance[MAX], pred[MAX]; int visited[MAX], count, mindistance, nextnode, i, j; // Creating cost matrix for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (Graph[i][j] == 0) cost[i][j] = INFINITY; else cost[i][j] = Graph[i][j]; for (i = 0; i < n; i++) { distance[i] = cost[start][i]; pred[i] = start; visited[i] = 0; } distance[start] = 0; visited[start] = 1; count = 1; while (count < n - 1) { mindistance = INFINITY; for (i = 0; i < n; i++) if (distance[i] < mindistance && !visited[i]) { mindistance = distance[i]; nextnode = i; } visited[nextnode] = 1; for (i = 0; i < n; i++) if (!visited[i]) if (mindistance + cost[nextnode][i] < distance[i]) { distance[i] = mindistance + cost[nextnode][i]; pred[i] = nextnode; } count++; } // Printing the distance for (i = 0; i < n; i++) if (i != start) { printf("\nDijkstra's Algorithm Distance from source to %d: %d", i, distance[i]); } }
调用:
//15 Dijkstra's Algorithm 迪杰斯特拉算法 最短路径算法 int Graph[MAX][MAX], j, u; n = 7; Graph[0][0] = 0; Graph[0][1] = 0; Graph[0][2] = 1; Graph[0][3] = 2; Graph[0][4] = 0; Graph[0][5] = 0; Graph[0][6] = 0; Graph[1][0] = 0; Graph[1][1] = 0; Graph[1][2] = 2; Graph[1][3] = 0; Graph[1][4] = 0; Graph[1][5] = 3; Graph[1][6] = 0; Graph[2][0] = 1; Graph[2][1] = 2; Graph[2][2] = 0; Graph[2][3] = 1; Graph[2][4] = 3; Graph[2][5] = 0; Graph[2][6] = 0; Graph[3][0] = 2; Graph[3][1] = 0; Graph[3][2] = 1; Graph[3][3] = 0; Graph[3][4] = 0; Graph[3][5] = 0; Graph[3][6] = 1; Graph[4][0] = 0; Graph[4][1] = 0; Graph[4][2] = 3; Graph[4][3] = 0; Graph[4][4] = 0; Graph[4][5] = 2; Graph[4][6] = 0; Graph[5][0] = 0; Graph[5][1] = 3; Graph[5][2] = 0; Graph[5][3] = 0; Graph[5][4] = 2; Graph[5][5] = 0; Graph[5][6] = 1; Graph[6][0] = 0; Graph[6][1] = 0; Graph[6][2] = 0; Graph[6][3] = 1; Graph[6][4] = 0; Graph[6][5] = 1; Graph[6][6] = 0; u = 0; Dijkstra(Graph, n, u);