Dijkstra算法详解：邻接矩阵求两点间最短路径

Dijkstra算法是一种用于寻找图中两个节点之间最短路径的贪心算法，特别适用于带有非负权重的有向或无向图。在这个C++实现的源代码中，我们看到以下几个关键知识点： 1. **数据结构定义**： - 使用`Node`类来表示图中的节点，包含成员变量`pre`（前驱节点），`w`（权值）和`v`（是否加入最短路径集）。初始化时，`w`被设为`MAX_INT`，表示未找到路径时的极大值，`v`初始为`false`。 2. **输入处理**： - 输入顶点数`n`和边数`m`，以及每条边的起始点、终点和权值。邻接矩阵`linjie`用于存储图的权重，所有自环权重为0。 3. **邻接矩阵表示**： - 使用二维数组`linjie`来表示图的邻接矩阵，通过矩阵元素`linjie[i][j]`获取节点`i`到节点`j`的权重。 4. **Dijkstra算法的核心逻辑**： - 主函数中，从给定的源点`start0`开始执行Dijkstra算法。首先将源点的权重设为0，然后进入循环： - 初始化`min`为极大值，`t`为下个待处理节点。 - 对于所有未加入最短路径集的节点，检查它们到已知最短路径节点的总权重。如果某个节点的新权重小于`min`，则更新该节点的权重、前驱节点，并记录新的`min`值。 - 将找到最小权重的节点`j`设置为下个加入最短路径集的节点`k`，并将其标记为已处理。 5. **算法终止条件**： - 当遍历完所有节点，或者找到目标节点（即`final`）时，算法结束。在此过程中，`s[j].pre`保存了从源点到节点`j`的最短路径的前驱节点。 6. **输出结果**： - 最终，可以根据`s`数组中的信息，构建出从源点到其他所有节点的最短路径，包括每个节点的前驱节点。 通过这段代码，你可以了解到如何在实际编程中应用Dijkstra算法来解决最短路径问题，这是一种基础且重要的算法，对于网络路由、地图导航等领域有着广泛的应用。理解和掌握这个源代码，有助于你进一步学习和优化路径搜索算法。