使用Dijkstra算法解决最短路径问题

"C++实现Dijkstra算法的代码示例" 这段代码展示了一个使用C++编写的Dijkstra最短路径算法的实例。Dijkstra算法是一种在加权图中寻找单源最短路径的算法，由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。在这个例子中，算法用于找到从节点0出发到所有其他节点的最短路径。 首先，代码导入了`iostream`、`vector`和`iterator`库，并定义了一些全局变量。`n`表示图中的节点数量，`g`是邻接矩阵，用来存储图的边和权重，`s`是起始节点，`known`是一个布尔数组记录每个节点是否已被访问，`dist`存储从起点到各节点的最短距离，`prev1`记录每个节点的前驱节点（即到达该节点的最短路径上前一个节点）。 `Dijkstra`函数是实现Dijkstra算法的主要部分： 1. 初始化`known`、`dist`数组，将所有节点标记为未访问，距离设为无穷大，起点距离设为0。 2. 使用一个无限循环，直到找到所有节点的最短路径或没有未访问节点。 - 在每次迭代中，找到当前未访问节点中距离起点最近的一个，将其标记为已访问。 - 遍历这个节点的所有邻居，如果邻居未访问且通过当前节点到达的距离小于已知的最短距离，则更新其最短距离和前驱节点。 3. 当找不到更近的未访问节点时（即`min==INT_MAX`），表示所有可达节点的最短路径都已找到，循环结束。 `Print_SP`函数用于打印从起点到指定节点的最短路径，通过遍历`prev1`数组反向追溯。 在`main`函数中，创建了一个5个节点的图，设置了各个边的权重，并调用`Dijkstra`计算最短路径。然后，输出每个节点的最短距离，并使用`Print_SP`显示从起点到这些节点的路径。 这个代码实例清楚地展示了如何在C++中实现Dijkstra算法，并提供了一个简单的图作为输入，使得读者可以直观理解算法的运行过程。