C++dijkstra最短路径算法

### C++实现Dijkstra最短路径算法 #### 算法背景 Dijkstra算法是由荷兰计算机科学家Edsger W. Dijkstra于1956年提出的，用于解决带权重的有向图或无向图中的单源最短路径问题。该算法能够找到从指定起点到图中所有其他顶点的最短路径，且要求图中的边权非负。 #### 数据结构定义 为了存储图的信息，代码中定义了一个结构体`mgraph`： ```cpp typedef struct { vextype vexs[vertex_max]; int arcs[vertex_max][vertex_max]; int vexnum, arcnum; } mgraph; ``` 其中： - `vextype vexs[vertex_max]`：顶点数组，每个顶点由一个长度为20的字符数组表示。 - `int arcs[vertex_max][vertex_max]`：邻接矩阵，用于表示图中顶点之间的连接关系以及边的权重。 - `int vexnum`：图中顶点的数量。 - `int arcnum`：图中边的数量。 #### 图的创建 创建图的过程主要分为以下几个步骤： 1. 输入顶点数量`n`和边的数量`m`。 2. 输入各顶点的信息。 3. 输入每条边的起点、终点及权重。 这部分代码通过读取用户输入完成图的构建，并初始化邻接矩阵`arcs`，使得不存在边连接的两个顶点之间权重设为`maxint`（一个非常大的数，表示无穷大）。 #### Dijkstra算法实现 Dijkstra算法的核心在于不断地选择未被访问过的顶点中距离起点最近的顶点，更新该顶点所有邻接点的距离信息。具体实现如下： ```cpp void dijkstra(mgraph g, int v0, int path[], int dist[]) { // 初始化 int i, j; int k = v0; int v, w, min; int s[vex_num]; for (v = 0; v < n; v++) { s[v] = 0; dist[v] = g.arcs[v0][v]; if (dist[v] < maxint) path[v] = v0; else path[v] = -1; } dist[v0] = 0; s[v0] = 1; // 主循环 for (i = 1; i < n; i++) { min = maxint; for (w = 0; w < n; w++) { if (!s[w] && dist[w] < min) { k = w; min = dist[w]; } } s[k] = 1; // 更新路径 for (j = 0; j < n; j++) { if (!s[j] && (min + g.arcs[k][j] < dist[j])) { dist[j] = min + g.arcs[k][j]; path[j] = k; } } } } ``` 算法的主要流程包括： 1. 初始化：设置起点到各个顶点的距离和路径。 2. 循环选择离起点最近的未访问顶点。 3. 更新所有与当前顶点相邻的顶点的距离和路径。 #### 输出路径 函数`putpath`用于输出从起点到目标顶点的最短路径及其长度。该函数利用之前计算得到的路径数组`path`和距离数组`dist`来展示路径。 #### 完整程序运行流程 主函数`main`中，首先创建一个图实例，然后读取起点和终点的信息，调用`dijkstra`函数计算最短路径，最后调用`putpath`函数输出结果。 整体而言，这段代码提供了一个完整的Dijkstra算法实现过程，包括图的构建、算法的执行以及结果的输出。对于理解Dijkstra算法及其在实际编程中的应用具有很好的参考价值。