大一数据结构：Dijkstra算法解决最短路径问题

"大一数据结构课程中的最短路径问题，使用Dijkstra算法求解" 在数据结构领域，最短路径问题是一个常见的图论问题，它寻找的是在给定图中两个顶点之间的路径，使得路径上的边权之和最小。这个问题在许多实际应用中都有所体现，例如在交通网络、通信网络以及计算机科学的其他领域。 在这个问题中，给出的代码是使用C语言实现的Dijkstra算法，Dijkstra算法是一种解决单源最短路径问题的有效方法。该算法以一个起点开始，逐步扩展最短路径到其他所有节点，直到找到从起点到图中所有其他节点的最短路径。 首先，我们来看代码定义的数据结构： 1. `MGraph` 结构体：表示一个图，包括顶点数组 `vexs` 和邻接矩阵 `arcs`。`vexs` 存储顶点的值，`arcs` 存储图中边的权重。 2. `D1` 和 `p1` 数组：在单源最短路径问题中，`D1` 用于存储从起点到各个顶点的最短距离，`p1` 用于记录前驱节点，即到达当前顶点的路径上前一个节点。 3. `D` 和 `p` 数组：用于存储多源最短路径问题的最短距离和前驱节点，但这段代码仅实现了单源最短路径。 4. `CreateMGraph` 函数：创建一个图，读取输入的顶点数 `n`、边数 `e` 和边的权重，填充邻接矩阵。 5. `Dijkstra` 函数：执行Dijkstra算法，找出从指定起点 `v1` 到其他所有顶点的最短路径。 Dijkstra算法的工作原理如下： - 初始化：将起点 `v1` 的最短距离设为0，其他所有顶点的最短距离设为无穷大（用 `Maxint` 表示），并将所有顶点标记为未访问（用 `FALSE` 表示）。 - 按顺序选择未访问顶点中具有最短距离的一个（初始时为起点），将其标记为已访问。 - 更新所有相邻未访问顶点的距离，如果通过已访问顶点到达的路径更短，则更新该顶点的最短距离和前驱节点。 - 重复上述步骤，直到所有顶点都被访问。 在代码中，`Dijkstra` 函数使用了布尔数组 `S` 来跟踪顶点是否被访问过，`D2` 和 `p2` 分别存储当前最短距离和前驱节点。函数内部使用了一个循环来逐步扩展最短路径，直到所有顶点都被处理。 最后，代码中打印出从起点 `v1` 到每个顶点的最短距离，这可以通过遍历 `D2` 数组并输出其值来完成。同样，通过 `p2` 数组可以追溯出到达每个顶点的最短路径。 这个代码段展示了如何使用Dijkstra算法解决最短路径问题，适用于具有非负边权重的图。在实际应用中，可能会遇到有负权重的边，此时Dijkstra算法不再适用，需要使用其他算法，如Bellman-Ford算法。