迪杰斯特拉最短路径计算器

欢迎使用 迪杰斯特拉最短路径计算器，这是一个使用迪杰斯特拉（Dijkstra）算法寻找加权图中最短路径的交互式工具。无论您是学习图论的计算机科学专业学生，还是分析路由协议的网络专业人士，亦或是实现寻路算法的开发人员，此计算器都能为您提供计算机科学中最基础算法之一的可视化分步探索。

什么是迪杰斯特拉算法？

迪杰斯特拉算法由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年发明，是一种解决具有 非负边权 的加权图单源最短路径问题的图搜索算法。给定一个源节点，它会找到从该节点到图中每个其他节点的最短路径。

该算法通过维护一组未访问的节点，并重复选择具有最小暂定距离的未访问节点（贪心策略）来工作。这就是它既优雅又高效的原因——一旦一个节点被“访问”，它的最短距离就保证是最终确定的。

算法伪代码

核心公式

其中：

• d[u] = 当前已知的从源到节点 u 的最短距离
• w(u, v) = 从 u 到 v 的边的权重
• d[v] = 当前已知的从源到节点 v 的最短距离

如何使用此计算器

1. 定义图的边： 以 源, 目的地, 权重 的格式输入边，每行一条。每一行代表两个节点之间的一个连接。
2. 选择图类型： 双向边（如道路）选择“无向图”，单向边（如飞行路线或网页链接）选择“有向图”。
3. 设置源节点： 输入计算所有最短路径的起点节点。
4. 寻找最短路径： 点击按钮运行迪杰斯特拉算法。探索交互式图形可视化、距离表和分步追踪。
5. 逐步查看： 使用“下一步/上一步”按钮查看算法一次执行一步，图中会实时高亮显示更新的节点和边。

理解结果

距离表

显示从源到每个节点的最短距离以及完整路径。标记为 ∞ 的节点表示从源节点不可达。

图形可视化

交互式画布通过颜色编码的节点和边显示您的图：

• 蓝色节点 = 源节点
• 绿色节点 = 已访问（最终确定的距离）
• 橙色节点 = 当前正在处理中
• 灰色节点 = 尚未访问
• 绿色边 = 最短路径树

分步追踪

显示算法的执行过程，包括每一步的优先队列提取、边松弛和距离更新。这对于学习算法的工作原理非常有价值。

时间复杂度

迪杰斯特拉算法的效率取决于用于优先队列的数据结构：

其中 V 是顶点（节点）的数量，E 是边的数量。此计算器使用二叉堆实现。

有向图 vs. 无向图

• 无向图： A 和 B 之间的边意味着您可以同时进行 A→B 和 B→A 的移动。示例：道路网络、好友关系网、电路。
• 有向图： 从 A 到 B 的边仅允许 A→B 的移动，不一定允许 B→A。示例：网页超链接、Twitter 关注、飞行路线、河流流量。

迪杰斯特拉算法的局限性

• 不能处理负边权： 迪杰斯特拉算法在存在负边权的情况下会产生错误结果。对于包含负权重（但无负环）的图，请使用 Bellman-Ford 算法。
• 单源： 它只能找到从一个源出发的最短路径。对于全源最短路径，请使用 Floyd-Warshall 算法或从每个节点运行一次迪杰斯特拉算法。
• 不能处理负环： 负环会使最短路径无法定义（您可以始终绕环移动以无限减小距离）。

实际应用

GPS 导航

地图服务使用迪杰斯特拉算法的变体（通常带有 A* 启发式搜索）来查找两个位置之间的最快路线。道路交叉口是节点，路段是加权边（按时间或距离计算）。

网络路由

互联网路由协议如 OSPF（开放最短路径优先）和 IS-IS 使用迪杰斯特拉算法计算网络拓扑中的最短路径。每台路由器都会构建一棵最短路径树来确定数据包转发。

社交网络分析

寻找用户之间的最短连接路径（六度分隔理论）、计算中心性度量以及识别网络中的影响节点。

游戏开发

视频游戏中的 NPC 寻路使用迪杰斯特拉算法或 A*（通过启发式扩展了迪杰斯特拉）来导航游戏地图并找到最优移动路径。

供应链与物流

优化配送路线、仓库到商店的路径以及不同运输方式具有不同成本的多式联运网络。

常见问题解答

什么是迪杰斯特拉算法？

迪杰斯特拉算法是一种图搜索算法，用于在具有非负边权的加权图中查找从源节点到所有其他节点的最短路径。它采用优先队列（最小堆）的贪心策略，始终处理已知距离最小的未访问节点。使用二叉堆时，其时间复杂度为 O((V + E) log V)。

迪杰斯特拉算法能处理负边权吗？

不能，迪杰斯特拉算法要求所有边权必须为非负。负权重会导致算法产生错误结果，因为一旦节点被标记为已访问，其距离就被认为是最终确定的。对于包含负权重（但无负环）的图，应改用 Bellman-Ford 算法。

有向图和无向图有什么区别？

在有向图中，边具有方向——从 A 到 B 的边并不意味着存在从 B 到 A 的边。在无向图中，边是双向的——如果 A 和 B 之间存在连接，则可以沿任一方向移动。道路网络通常建模为无向图，而网页链接和飞行路线通常是有向的。

迪杰斯特拉算法中的边松弛是什么？

边松弛是迪杰斯特拉算法的核心操作。访问节点 u 时，对于每个邻居 v，算法会检查通过 u 的路径 (dist[u] + weight(u,v)) 是否比当前已知的到 v 的距离 (dist[v]) 更短。如果更短，则更新（松弛）该距离，并将 v 以新距离加入优先队列。

什么是最短路径树？

最短路径树 (SPT) 是以源节点为根的子图，包含从源节点到所有可达节点的最短路径。每个节点（源节点除外）恰好有一个父节点，即其最短路径上的前驱节点。SPT 是迪杰斯特拉算法的副产品，对路由和网络设计非常有用。

迪杰斯特拉算法有哪些实际应用？

迪杰斯特拉算法用于 GPS 导航系统、网络路由协议 (OSPF, IS-IS)、社交网络分析、航空路线优化、机器人路径规划、游戏 AI 寻路、供应链物流和电信网络设计。任何可以建模为在图中寻找最短或最低成本路径的问题都能从该算法中受益。

更多资源

• 迪杰斯特拉算法 - 维基百科
• 最短路径问题 - 维基百科