【dijkstra算法】Dijkstra算法是一种用于计算图中单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）于1956年提出。该算法适用于具有非负权重的有向或无向图，广泛应用于网络路由、地图导航等领域。
一、Dijkstra算法简介
Dijkstra算法的核心思想是通过贪心策略逐步找到从起点到各个节点的最短路径。它维护一个距离数组，记录当前已知的最短路径长度，并不断选择当前距离最小的节点进行扩展，直到所有节点都被处理完毕。
二、Dijkstra算法步骤总结
| 步骤 | 操作说明 |
| 1 | 初始化：设置起点到各节点的距离为无穷大（∞），起点到自身的距离为0。 |
| 2 | 创建一个优先队列（或最小堆）来存储待处理的节点及其当前距离。 |
| 3 | 将起点加入优先队列。 |
| 4 | 从优先队列中取出距离最小的节点u。 |
| 5 | 遍历u的所有邻接节点v，若通过u到达v的路径比当前已知的v的距离更短，则更新v的距离，并将v加入优先队列。 |
| 6 | 重复步骤4-5，直到优先队列为空或目标节点被处理。 |
三、Dijkstra算法特点
| 特点 | 描述 |
| 适用性 | 仅适用于边权值为非负数的图 |
| 时间复杂度 | O(E + V log V)（使用优先队列优化） |
| 空间复杂度 | O(V + E) |
| 贪心策略 | 每一步都选择当前最短路径的节点进行扩展 |
| 最短路径 | 可以得到从起点到所有其他节点的最短路径 |
四、Dijkstra算法优缺点
| 优点 | 缺点 |
| 算法简单易实现 | 不适用于存在负权边的图 |
| 时间效率较高 | 无法处理负权环 |
| 可以处理大规模图 | 需要额外空间存储距离和前驱节点 |
五、Dijkstra算法应用场景
| 应用场景 | 说明 |
| 地图导航 | 如百度地图、高德地图中的路径规划 |
| 网络路由 | 如路由器中选择最优路径传输数据 |
| 社交网络 | 分析用户之间的最短联系路径 |
| 项目管理 | 计算关键路径（如Pert图） |
六、Dijkstra算法与Bellman-Ford算法对比
| 对比项 | Dijkstra算法 | Bellman-Ford算法 |
| 边权限制 | 必须为非负数 | 可以包含负权边 |
| 时间复杂度 | O(E + V log V) | O(V × E) |
| 是否支持负权环 | 不支持 | 支持（但检测负权环） |
| 实现难度 | 相对简单 | 较复杂 |
| 适用范围 | 适合大多数实际问题 | 适合理论分析和特殊场景 |
总结
Dijkstra算法是一种高效且实用的最短路径算法，特别适合在没有负权边的图中使用。虽然其在某些特定情况下（如存在负权边）不适用，但在实际应用中仍然非常广泛。掌握该算法不仅有助于理解图论的基本概念，还能在实际开发中解决许多路径规划问题。
