Dijkstra算法

Dijkstra算法是一种经典的图论算法，用于寻找图中两个节点之间的最短路径。在这个C++程序中，Dijkstra算法被实现来找到一个给定起点到其他所有节点的最短路径。程序采用邻接矩阵作为图的数据结构，并通过优先队列（未在代码中显示）或者贪心策略来有效地寻找最小距离的节点。 1. **邻接矩阵表示图**： 在这个程序中，`linjie`是一个二维动态数组，用来存储图的邻接矩阵。每个元素`linjie[i][j]`表示节点i到节点j的权重。如果`linjie[i][j] = MAX_INT`，则表示没有直接连接的边，或者权重为无穷大。对角线元素`linjie[i][i]`被初始化为0，表示节点到自身的距离为0。 2. **Dijkstra算法的核心步骤**： - 初始化：创建一个`Node`类，包含权值`w`、前驱节点`pre`和标记变量`v`。`v`用于标识该节点是否已经被包含在最短路径集合中。 - 设置源点`start0`的权重为0，其他所有节点的权重设为无穷大（`MAX_INT`）。 - 进行循环，每次选择当前未被加入最短路径集合且具有最小权重的节点k，更新与其相邻的节点权重。如果通过节点k到达节点j的路径比已知的最短路径更短，则更新节点j的权重和前驱节点。 - 当所有节点都被加入最短路径集合后，算法结束。 3. **路径的反向追踪**： 为了输出从起点到任意指定终点的最短路径，程序通过跟踪每个节点的前驱节点（`pre`）来实现反向打印路径。从终点开始，依次输出其前驱节点，直到找到起点为止。 4. **输入处理**： 用户输入图的顶点数`n`和边数`m`，以及每条边的起始点、结束点和权重。程序还允许用户输入起点`start0`和终点，以便展示从起点到终点的最短路径。 总结来说，Dijkstra算法通过贪心策略逐次扩展最短路径，每次选择当前未处理节点中距离源点最近的一个，更新与其相邻节点的距离。在C++代码中，它被实现为一个迭代过程，不断寻找并更新最短路径，直到所有节点都被处理。通过反向追踪前驱节点来输出最短路径。这个程序提供了一个清晰的Dijkstra算法实现，适用于加权无环图（因为Dijkstra算法不保证在有负权边的情况下找到最短路径）。