概念

最短路径

Dijkstra（非负权）、Bellman-Ford（可负权）、Floyd-Warshall（全源）三种经典算法覆盖了导航与网络路由的核心需求。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

最短路径图论

01定义

最短路径问题求两点间权重和最小的路径：Dijkstra 算法以贪心扩展处理非负权图，Bellman-Ford 容忍负权并检测负环，Floyd-Warshall 一次算出所有点对——三者覆盖导航与路由的核心需求。

Dijkstra：金边构成 s 到 t 的最短路径

Dijkstra（非负权，堆优化 $O((V+E)\log V)$ ）；Bellman-Ford（允许负权、检测负环， $O(VE)$ ）；Floyd-Warshall（全源， $O(V^3)$ ，动态规划）。

最短路径的任一子段仍是最短路径——动态规划与 Dijkstra 贪心的共同根基；负权圈则使「最短」失去意义。

A* 用启发函数剪枝（可采纳则最优）；路网查询另有收缩层级（CH）与地标法（ALT），把大陆级查询压到毫秒。

d(v)=\min_{(u,v)\in E}\bigl(d(u)+w(u,v)\bigr)

Dijkstra 1956 年喝咖啡时 20 分钟想出算法并 1959 年发表；Bellman 与 Ford 1958 年以动态规划处理负权；Floyd 与 Warshall 1962 年给出全源算法。

地图导航（高德/谷歌路线规划）、网络路由协议（OSPF 即 Dijkstra）、游戏 AI 寻路、供应链最小成本运输。

Dijkstra：逐步扩张最短路径树增大步数：每次确定一个距 A 最近的节点，直到全图

step 已确定节点数0