贪心算法实践：单源最短路径与迪杰斯特拉算法

“实验三：贪心算法 .docx”是一个关于使用C++实现贪心算法解决单源最短路径问题和作业调度问题的文档。实验旨在让学生掌握贪心算法的基本特征和步骤，并通过编程实践来解决这两个问题。 贪心算法是一种优化策略，它在每一步选择局部最优解，期望这些局部最优解能导致全局最优解。在这个实验中，学生将学习如何运用贪心算法来解决以下两个问题： 1. **单源最短路径问题**：这是一个经典的图论问题，目标是从图中的一个特定源点（起点）到所有其他顶点找到最短路径。实验中提到的迪杰斯特拉算法是解决此类问题的一种有效方法。算法的工作原理是： - 初始化所有顶点到源点的距离，并建立前驱数组来记录到达每个顶点的路径。 - 开始时，源点的距离设为0，其他顶点的距离设为无穷大（或一个足够大的数，如这里的`max`）。 - 在每一轮中，算法选择当前未处理顶点中距离源点最近的一个，更新其邻居的最短距离。如果发现新的更短路径，就更新前驱数组。 - 这个过程重复，直到所有顶点都被处理。最终，`dis[i]`存储了源点到顶点i的最短距离，`p[i]`记录了路径。 2. **作业调度问题**：这是一个在多个任务之间分配资源的问题，目标是通过合理的调度，使得完成所有任务的总时间最小。贪心算法可以用于找出近似最优的解决方案，例如，按照任务的预计完成时间（非递增顺序）来安排任务，每次选择最早完成的任务优先执行。 实验的代码部分展示了迪杰斯特拉算法的实现，其中`Dijkstra`函数接受图的邻接矩阵`c`、顶点数`n`、源点`v`、前驱数组`p`和最短距离数组`dis`作为参数。函数内部包含了初始化、距离更新和迭代查找最近顶点的过程。 时间复杂性方面，由于迪杰斯特拉算法通常需要遍历所有顶点和邻接边，所以时间复杂度通常是O(n^2)，其中n是顶点的数量。这表明贪心算法虽然在每一步选择局部最优，但对大规模问题可能会效率较低。 在实践中，为了提高效率，可以使用优先队列（如二叉堆）来存储待处理的顶点，这样可以在O(log n)的时间内找到最近的顶点，从而将算法的时间复杂度降低到O((n+e)log n)，其中e是边的数量。对于稀疏图（边的数量远小于顶点数量的平方），这种方法非常有效。