C++实现Dijkstra算法无向图版本

"无向图Dijkstra算法的C++实现及路径回溯" Dijkstra算法是一种经典的最短路径算法，由荷兰计算机科学家艾兹格·迪科斯彻（Edsger W. Dijkstra）提出，主要用于解决单源最短路径问题。在给定的无向或有向图中，该算法能够找到从起点到其余所有顶点的最短路径。在这个C++代码实现中，Dijkstra算法被用于处理无向图，但通过稍作修改，也可以应用于有向图。 首先，我们来看代码中的主要变量： 1. `m` 和 `n` 分别表示图中的顶点数量和边的数量。 2. `a[100][100]` 是邻接矩阵，存储图中每个顶点之间的权重。在无向图中，这个矩阵是对称的，因为每条边连接两个顶点，所以`a[i][j] = a[j][i]`。 3. `dist[100]` 存储从起点到各个顶点的最短距离，初始化为无穷大（`MAX`），起点的初始距离设为0。 4. `prev[100]` 保存最短路径上的前一个顶点，用于回溯路径。 接下来是`dijkstra()`函数，它实现了Dijkstra算法的主要逻辑： 1. 首先检查输入是否合法，即检查边的数量是否小于0或者大于顶点数量。 2. 初始化距离数组`dist`和前驱数组`prev`，并设置一个布尔数组`s`来标记顶点是否已被处理。 3. 使用一个循环逐步找到最短路径。在每次迭代中，找到当前未处理顶点中距离最小的一个，然后更新与其相邻的未处理顶点的距离。 4. 更新过程通过比较新路径（当前顶点到相邻顶点的距离之和）和旧路径（之前计算的最短距离）来进行，如果新路径更短，则更新距离，并记录前驱顶点。 `path()`函数则用于打印从起点到其他顶点的最短路径和距离，通过`prev[]`数组回溯路径。 在`main()`函数中，用户输入顶点数量`n`和边的权重，程序会调用`dijkstra()`计算最短路径，然后调用`path()`输出结果。 需要注意的是，这个实现假设输入的图是连通的，即每个顶点都可以通过一系列边到达其他所有顶点。如果图不连通，Dijkstra算法可能无法找到某些顶点的最短路径。此外，对于负权边，Dijkstra算法不再适用，因为其依赖于贪心策略，而负权边可能导致无法得到全局最优解。在这种情况下，可以考虑使用其他算法，如Bellman-Ford算法。