c++最短路径算法.pdf

C++中的最短路径算法是图论中的一种经典算法，主要用来寻找图中从一个顶点到其他所有顶点的最短路径。本文件中提到的两种算法是Dijkstra算法和Floyd算法。 1. Dijkstra算法： Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger W. Dijkstra）于1956年发明的，主要用于解决单源最短路径问题。在无权图或非负权重图中，它能找出从源点到所有其他顶点的最短路径。算法的核心思想是使用优先队列（通常用最小堆实现）来选取当前未访问顶点中距离源点最近的一个，并更新与之相邻的顶点的距离。 代码中的`dijkstraTree`函数实现了Dijkstra算法的基本流程： - 初始化：设置一个距离数组`D`，其中`D[i]`表示顶点1到顶点i的初始距离；并设置一个标记数组`mark`，用于记录顶点是否已加入到最短路径树中。 - 主循环：遍历所有顶点，每次选择未被标记的顶点中距离源点最近的一个（最小堆操作），然后更新与其相邻且未被标记的顶点的距离。 - 更新：如果新路径比旧路径短，则更新该顶点的距离。 - 结束条件：当无法找到更近的顶点时，算法结束。 2. Floyd算法： Floyd算法，也称为Floyd-Warshall算法，是用于解决所有顶点对之间的最短路径问题的算法。在有向图或无向图中，无论边的权重是非负还是可以为负，只要没有负权回路，Floyd算法都能找到最短路径。其基本思想是通过迭代逐步考虑所有的中间节点来尝试缩短路径。 代码中的`Floyd`函数实现了Floyd算法： - 初始化：创建一个矩阵`A`，初始值等于邻接矩阵`GraphC`，即每个顶点对的直接距离。 - 迭代：对于每一个顶点k，检查所有顶点对(i, j)，如果通过k的路径比直接连接的路径短，则更新`A[i][j]`。 - 输出：最后得到的矩阵`A`即为所有顶点对的最短路径长度。 在`main`函数中，用户输入图的顶点数和边数，然后调用`creatGraph`函数构造图的邻接矩阵，接着分别使用`dijkstraTree`和`Floyd`函数计算单源最短路径和所有顶点对的最短路径。 这两种算法在实际应用中非常广泛，如网络路由、交通路线规划等领域。Dijkstra算法适用于处理大量顶点的情况，因为它只需要关注距离源点最近的顶点，而Floyd算法则能找出所有可能的最短路径，但计算量相对较大。