#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_VERTICES 100 #define INF INT_MAX typedef struct Graph { int V; //顶点数 int E; //边数 int adj[MAX_VERTICES][MAX_VERTICES];//邻接矩阵 } Graph; void init_graph(Graph* G, int V) { G->V = V; G->E = 0; for (int i = 0; i < G->V; i++) { for (int j = 0; j < G->V; j++) { G->adj[i][j] = INF; } } } void add_edge(Graph* G, int u, int v, int w) { G->adj[u][v] = w; G->adj[v][u] = w; G->E++; } void dijkstra(Graph* G, int s, int dist[]) { int visited[MAX_VERTICES] = { 0 }; for (int i = 0; i < G->V; i++) { dist[i] = INF; } dist[s] = 0; for (int i = 0; i < G->V; i++) { int u = -1; for (int j = 0; j < G->V; j++) { if (!visited[j] && (u == -1 || dist[j] < dist[u])) { u = j; } } visited[u] = 1; for (int v = 0; v < G->V; v++) { if (G->adj[u][v] != INF) { if (dist[u] + G->adj[u][v] < dist[v]) { dist[v] = dist[u] + G->adj[u][v]; } } } } } int main() { Graph G; int V = 6; init_graph(&G, V); add_edge(&G, 0, 1, 10); add_edge(&G, 0, 2, 3); add_edge(&G, 1, 2, 1); add_edge(&G, 1, 3, 2); add_edge(&G, 2, 1, 4); add_edge(&G, 2, 3, 8); add_edge(&G, 2, 4, 2); add_edge(&G, 3, 4, 7); add_edge(&G, 3, 5, 1); add_edge(&G, 4, 5, 5); int dist[MAX_VERTICES]; dijkstra(&G, 0, dist); printf("最短路径长度为：%d\n", dist[V - 1]); return 0; }代码解读

这是一个使用邻接矩阵实现的Dijkstra算法的代码。首先定义了一个图的结构体，包括顶点数、边数和邻接矩阵。然后定义了初始化图的函数和添加边的函数。接着是Dijkstra算法的实现，在算法中用visited数组记录已经访问过的顶点，用dist数组记录源点到各个顶点的最短距离，算法的核心循环是通过选择dist数组中最小的未访问过的顶点来进行松弛操作。最后在主函数中构造了一个图，并计算了从顶点0到顶点5的最短路径长度。