C语言实现数据结构 最短路径

根据给定的信息，本文将详细解释如何利用C语言实现一种数据结构来求解最短路径问题。本案例中采用的数据结构是邻接表，并通过Dijkstra算法计算最短路径。 ### 1. 邻接表表示图 我们需要定义一个邻接表来存储图的结构。邻接表是一种常用的图数据结构，它通过链表的形式表示图中的边。在邻接表中，每个顶点都对应着一个链表，该链表包含了与该顶点相连的所有边。 #### 定义节点结构体 ```c typedef struct ArcNode { int adjvex; // 相邻顶点的位置 struct ArcNode* nextarc; // 指向下一个节点的指针 int weight; // 边的权重 } ArcNode; typedef struct VNode { char data; // 顶点的数据 ArcNode* firstarc; // 指向第一个相邻顶点的指针 } VNode, AdjList[max]; typedef struct { AdjList vertices; // 图的顶点数组 int vexnum; // 顶点数 int arcnum; // 边数 } ALGraph; ``` ### 2. 创建图 创建图的过程包括输入图的基本信息（如顶点数、边数）以及各个顶点之间的连接关系。通过`CreateList`函数可以实现这一过程： ```c void CreateList(ALGraph &G) { // 输入顶点数和边数 printf("请输入顶点数："); scanf("%d", &G.vexnum); printf("请输入边数："); scanf("%d", &G.arcnum); // 输入顶点数据 for (int i = 0; i < G.vexnum; i++) { getchar(); // 吸收换行符 scanf("%c", &G.vertices[i].data); G.vertices[i].firstarc = NULL; // 初始化链表为空 } // 输入边的数据 for (int k = 0; k < G.arcnum; k++) { getchar(); // 吸收换行符 char v1, v2; scanf("%c%c", &v1, &v2); printf("%c --> %c\n", v1, v2); int i = LocateVex(G, v1); int j = LocateVex(G, v2); ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = j; getchar(); // 吸收换行符 printf("请输入权值："); scanf("%d", &s->weight); s->nextarc = NULL; if (!G.vertices[i].firstarc) { // 如果链表为空，则直接插入 G.vertices[i].firstarc = s; } else { ArcNode* p = G.vertices[i].firstarc; while (p->nextarc) p = p->nextarc; // 找到最后一个节点 p->nextarc = s; // 插入新节点 } } } ``` ### 3. Dijkstra算法实现 Dijkstra算法是一种用来解决单源最短路径问题的经典算法。在这个部分，我们将使用Dijkstra算法找到从给定点到图中所有其他点的最短路径。 #### 初始化距离数组和路径矩阵 ```c void Dijkstra(ALGraph G, char v, char roud[max][max], int length[max]) { int m, n, i, j, k, temp, min, s1, s2; ArcNode* p, * q; int final[max]; s1 = LocateVex(G, v); // 找到起点的位置 // 初始化长度和路径数组 for (i = 0; i < G.vexnum; i++) { roud[i][0] = v; length[i] = 99; final[i] = 0; } final[s1] = 1; length[s1] = 0; p = G.vertices[s1].firstarc; while (p) { m = p->adjvex; length[m] = p->weight; p = p->nextarc; } // 主循环 for (i = 1; i < G.vexnum; i++) { min = 99; for (j = 0; j < G.vexnum; j++) { if (!final[j] && length[j] < min) { min = length[j]; n = j; } } final[n] = 1; // 将当前最短路径的终点标记为已访问 // 更新相邻顶点的距离 p = G.vertices[n].firstarc; while (p) { k = p->adjvex; if (!final[k] && length[n] + p->weight < length[k]) { length[k] = length[n] + p->weight; // 更新路径 for (s2 = 0; s2 < max; s2++) roud[k][s2] = roud[n][s2]; roud[k][i] = G.vertices[k].data; } p = p->nextarc; } } } ``` ### 4. 输出结果 我们可以通过`Printf`函数来输出图的信息，以及通过`PrintfList`和`Printf`函数输出最短路径的结果。 #### 输出图的信息 ```c void PrintfList(ALGraph G) { int i; ArcNode* p; printf("邻接表:\n"); for (i = 0; i < G.vexnum; i++) { printf("%d%c:", i, G.vertices[i].data); p = G.vertices[i].firstarc; while (p != NULL) { printf("%c%d", G.vertices[p->adjvex].data, p->weight); p = p->nextarc; } printf("\n"); } } void Printf(ALGraph G, int length[max], char roud[max][max]) { int i, j; printf("最短路径(顶点编号对应的字符):\n"); printf("99表示不可达\n"); for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) { printf("%c", roud[i][j]); } printf("最短路径长度:%d\n", length[i]); } } ``` 通过以上步骤，我们可以使用C语言实现邻接表表示的图数据结构，并基于此数据结构实现Dijkstra算法来求解最短路径问题。这种方法不仅适用于理论学习，也适合于实际编程应用。