数据结构实验报告：图应用 - 寻找最短路径 (C语言实现)

实验题目：图应用——寻找最短路径

实验目的：

1. 了解图的基本概念及其存储方式；
2. 学习最短路径算法——Dijkstra 算法；
3. 实现 Dijkstra 算法，并应用于寻找最短路径的问题。

实验内容：

1. 实现图的存储，包括邻接矩阵和邻接表两种方式；
2. 实现 Dijkstra 算法，求解图中任意两点之间的最短路径；
3. 编写主程序，实现用户输入起点和终点，输出最短路径及其长度。

实验步骤：

1. 图的存储：

   (1) **邻接矩阵：**定义一个二维数组 G[V][V]，其中 V 为顶点数，如果 V1 到 V2 有边，则 G[V1][V2] 为边的权值，否则设为无穷大。

   (2) **邻接表：**定义一个结构体数组，其中每个结构体包括一个顶点和它所连的边。在该结构体中可以用指针来表示下一个结构体，从而实现邻接表的存储。

2. Dijkstra 算法：

   (1) **初始化：**将起点到各个节点的距离设为无穷大，将起点到自身的距离设为 0。

   (2) **遍历：**从起点开始，依次遍历所有与其相邻的节点，更新其到起点的距离。如果更新后的距离比原先的距离小，则更新该节点的距离，并将该节点加入到待遍历的集合中。

   (3) **重复：**重复上述步骤，直到所有节点都被遍历过。

3. 主程序：

   (1) 创建图，实现邻接矩阵和邻接表两种存储方式。

   (2) 输入起点和终点。

   (3) 调用 Dijkstra 算法，求解最短路径及其长度。

   (4) 输出最短路径和长度。

代码实现：

1. 图的存储：

   (1) 邻接矩阵实现：

   typedef struct {
       int vexnum; // 顶点数
       int edgenum; // 边数
       int matrix[MAXVEX][MAXVEX]; // 邻接矩阵
   } MGraph;
   

   (2) 邻接表实现：

   typedef struct ArcNode {
       int adjvex; // 该弧所指向的顶点的位置
       int weight; // 弧的权值
       struct ArcNode *next; // 指向下一条弧的指针
   } ArcNode;
   
   typedef struct VertexNode {
       char data; // 顶点信息
       ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
   } VertexNode, AdjList[MAXVEX];
   
   typedef struct {
       AdjList vertices; // 邻接表
       int vexnum; // 图的当前顶点数
       int edgenum; // 图的当前边数
   } ALGraph;
   

2. Dijkstra 算法实现：

   void Dijkstra(MGraph G, int v0, int *dist, int *prev) {
       int i, j, k;
       int min;
       int tmp;
       int flag[MAXVEX]; // flag[i] 表示顶点 i 是否已经在 S 集合中
       for (i = 0; i < G.vexnum; i++) {
           flag[i] = 0; // 初始化
           dist[i] = G.matrix[v0][i]; // 初始化起点到各个顶点的距离
           prev[i] = 0; // 初始化前驱顶点
       }
       flag[v0] = 1; // 将起点加入到 S 集合中
       dist[v0] = 0; // 起点到自身的距离为 0
       for (i = 1; i < G.vexnum; i++) {
           min = INFINITY; // 初始化最小值为无穷大
           for (j = 0; j < G.vexnum; j++) {
               if (!flag[j] && dist[j] < min) { // 寻找距离最小的顶点
                   min = dist[j];
                   k = j;
               }
           }
           flag[k] = 1; // 将距离最小的顶点加入到 S 集合中
           for (j = 0; j < G.vexnum; j++) {
               tmp = (G.matrix[k][j] == INFINITY ? INFINITY : (min + G.matrix[k][j])); // 更新距离
               if (!flag[j] && tmp < dist[j]) {
                   dist[j] = tmp;
                   prev[j] = k; // 更新前驱顶点
               }
           }
       }
   }
   

3. 主程序：

   int main() {
       int i, j;
       int v0, v1;
       int dist[MAXVEX];
       int prev[MAXVEX];
       MGraph MG;
       ALGraph AG;
       // 创建邻接矩阵
       CreateMGraph(&MG);
       // 创建邻接表
       CreateALGraph(&AG);
       // 输入起点和终点
       printf("请输入起点和终点：\n");
       scanf("%d%d", &v0, &v1);
       // 求解最短路径及其长度
       Dijkstra(MG, v0, dist, prev);
       printf("起点到终点的最短路径为：");
       i = v1;
       printf("%d<-", i);
       while (prev[i] != v0) {
           printf("%d<-", prev[i]);
           i = prev[i];
       }
       printf("%d\n", v0);
       printf("最短路径的长度为：%d\n", dist[v1]);
       return 0;
   }