无需登录 数据私有 本地保存

Dijkstra最短路径动画 - 图论寻路展示

11
0
0
0
未访问 已探索 当前处理 起点 终点 最短路径 障碍物 困难地形(×3)
控制面板
慢快
探索节点: 0 路径长度: - 路径代价: - 状态: 就绪
提示：点击画布放置障碍物；拖拽起点或终点可移动位置。困难地形通过代价为普通格子的3倍。
常见问题与知识点

Dijkstra算法是由荷兰计算机科学家Edsger W. Dijkstra于1956年提出的经典图论算法，用于在带权图中寻找从单一源点到所有其他节点的最短路径。它采用贪心策略，每次选择距离起点最近且未处理的节点进行扩展，逐步确定全局最优解。该算法广泛应用于导航系统、网络路由协议（如OSPF）、游戏AI寻路等领域。

  1. 初始化：将起点距离设为0，其余节点设为无穷大；创建优先队列并将起点入队。
  2. 取出最小节点：从优先队列中取出距离最小的节点（首次为起点）。
  3. 松弛操作：遍历该节点的所有邻居，若通过当前节点到达邻居的距离更短，则更新邻居的距离值并记录前驱节点。
  4. 标记已处理：该节点标记为已访问，不再重复处理。
  5. 重复：继续从队列取出最小节点，直到队列为空或找到目标节点。
  6. 回溯路径：从终点沿前驱指针回溯到起点，得到最短路径。

使用二叉堆作为优先队列时，时间复杂度为 O((V+E) log V)，其中V为节点数，E为边数。使用斐波那契堆可优化至O(E + V log V)。对于稠密图（E≈V²），简单的数组实现O(V²)也可能更优。在本工具的网格图中，V=600, E≈2400，二叉堆实现非常高效。

当图中所有边的权重相等时，Dijkstra算法退化为广度优先搜索(BFS)。关键区别在于：BFS使用普通队列（FIFO），假设每步代价相同；而Dijkstra使用优先队列处理不同权重的边。本工具中设置了"困难地形"（权重×3），正是为了展示Dijkstra如何在非均匀代价下智能绕行，而非简单选择步数最少的路径。

  • 地图导航：Google Maps、高德地图等计算驾车/步行路线。
  • 网络路由：OSPF（开放最短路径优先）协议使用Dijkstra计算数据包的最优传输路径。
  • 游戏开发：RTS游戏中的单位寻路、NPC移动规划。
  • 物流规划：配送路线优化、仓库机器人调度。
  • 电路设计：PCB布线中寻找信号最短延迟路径。

Dijkstra算法基于贪心假设：一旦节点被标记为"已处理"，其最短距离就被认为是最终确定的。但在存在负权边的情况下，后续通过其他路径可能获得更短距离，这使得贪心策略失效。例如，一条路径先经过正权边再经过负权边，总代价可能比直接路径更小。处理负权边应使用Bellman-Ford算法（可检测负权环）或SPFA算法。
🔧 相关工具