Dijkstra算法详解与实现

Dijkstra（迪杰斯特拉）算法是一种用于解决单源最短路径问题的算法，由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它主要用于寻找图中一个起点到其他所有顶点的最短路径，特别适用于权重非负的图。这个算法的核心思想是使用贪心策略，每次扩展当前已知最短路径中的下一个节点，并更新与该节点相邻节点的最短路径。 在Dijkstra算法中，通常会维护两个集合：一个OPEN集合（未访问但已知距离的节点）和一个CLOSED集合（已访问并确定了最短路径的节点）。算法开始时，源节点位于OPEN集合中，其距离设为0，其他所有节点的距离设为无穷大（表示未知）。然后，算法不断选择OPEN集合中距离最小的节点，将其移入CLOSED集合，并更新与其相邻的节点的距离。如果相邻节点通过当前节点到达的距离比已知的更短，就更新这个距离。 给出的代码片段展示了Dijkstra算法的一个简单实现，主要包含以下几个部分： 1. `Map`数组存储图的邻接矩阵，表示节点之间的边和权重。 2. `is_arrived`数组记录每个节点是否已被访问。 3. `Dist`数组存储从源节点到各个节点的最短距离。 4. `From`数组记录到达每个节点的前驱节点，用于回溯路径。 5. `Stack`数组用于存储最短路径。 6. 函数`FindMin`找到OPEN集合中距离最小的节点。 7. 主函数`main`读取图的输入，初始化距离和前驱节点，然后执行Dijkstra算法。 代码中，首先用`memset`初始化所有节点的已访问标志为未访问，并读取源节点和顶点数量。接着，遍历邻接矩阵，将没有直接连接的节点之间的距离设为无穷大。之后，源节点的距离设为0，其他节点距离设为无穷大，前驱节点设为源节点或自身（表示未通过源节点到达）。 算法的主体是一个循环，当SETCARD（集合中的节点数）不为0时继续运行。在循环中，找到当前OPEN集合中距离最小的节点，将其标记为已访问，并对它的邻居进行检查，如果通过当前节点可以到达更短的路径，就更新邻居的最短距离和前驱节点。 需要注意的是，此代码实现没有处理权重为负的情况，因为Dijkstra算法本身不适用于负权重的图。对于负权重，可以考虑使用其他算法，如Bellman-Ford算法。 总结来说，Dijkstra算法是一种经典的图算法，适用于寻找单源最短路径，尤其在权重非负的情况下。它通过贪心策略逐步扩展最短路径，直到找到所有节点的最短路径。在实际应用中，如路由选择、网络优化等领域都有广泛的应用。