数据结构实验3.5：飞机换乘最短距离(Dijkstra单源最短路径).doc

该实验报告涉及的是数据结构中的一个重要算法——Dijkstra单源最短路径算法，该算法用于寻找图中一个起点到其他所有点的最短路径。在这个实验中，具体的应用场景是智能交通系统中的最佳路径选择问题，即从一个起始地点出发，通过一系列路径到达多个目的地，目标是找到耗费时间最少或路径长度最短或交通费用最小的方案。 实验的目的是设计一个程序，能够处理n个地点和m条路径的数据，这些数据包括路径的起点、终点和代价。这些信息存储在一个邻接矩阵中，这是一个二维数组，其中的元素表示图中两个节点之间的边和相应的权重（在这里可以是距离或费用）。 在给出的部分代码中，`Choose`函数用于找出当前未被处理的节点中，具有最小距离（或费用）的节点。它遍历整个数组，如果找到一个节点的距离小于或等于当前最小值且该节点尚未被处理（标记为0），则更新最小值和对应的节点位置。这里的改动是将参数从指针改为了数组，并在循环中将初始下标设为了0。 `Dijkstra`函数是Dijkstra算法的核心。它接收一个邻接矩阵表示的图`g`，起始节点`v`，以及两个距离和路径数组`d`和`path`。初始化时，所有节点的距离被设置为从`v`到相应节点的邻接矩阵值，路径数组记录每一步的前驱节点。源点`v`的距离被设置为0，并标记为已处理。然后，算法进入主循环，每次迭代选择未处理节点中距离最短的节点，并更新所有与其相邻且未处理的节点的距离。当所有节点都被处理后，输出最短距离的总和。 完整的程序包含了必要的头文件和常量定义，如错误状态码，极大值`INFTY`等。`main`函数中，用户将输入地点和路径数据，调用`Dijkstra`函数来计算最短路径，然后输出结果。 通过这个实验，学生可以深入理解Dijkstra算法的工作原理，掌握如何利用邻接矩阵表示图，并实现一个高效的路径搜索算法。同时，这也能提高他们的编程技能，包括动态规划、内存管理（如动态分配内存）和输入/输出处理。