迪杰斯特拉算法的优缺点

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两点之间最短路径的算法，它的优点和缺点如下：

**优点**：
1. **效率高**：迪杰斯特拉适用于加权非负边的图，对于稠密图（边数接近于节点数的平方）表现良好，因为它每次从未访问节点中选择当前距离源点最近的一个作为扩展点。
2. **渐进优化**：算法保证每一步找到的是局部最优解，最终达到全局最优解。
3. **简单直观**：算法思路清晰，易于理解和实现。

**缺点**：
1. **空间复杂度较高**：Dijkstra需要存储每个节点到起点的距离，如果图非常大，可能会消耗大量内存，尤其是无权图（所有边权重为1）的版本。
2. **不适合负权边**：算法无法处理负权边，因为负权边可能导致错误的结果，如形成无限循环或使路径看起来更短但实际上更长。
3. **动态更新困难**：对于边的添加或删除，迪杰斯特拉算法通常不适用，需要重新计算整个路径。