01先从一个问题出发
道路耗时不一样时，最少经过道路不代表最早到达。需要按累计代价扩展。
一个具体的例子
0→1 耗时 4，0→2 耗时 2，2→1 耗时 1；经过 2 到 1 只需 3。
02最直接的办法，为什么慢？
枚举所有简单路径计算代价。
暴力 · 最坏 O(V!) 条路径
大量路径共享相同前缀，候选数量可呈阶乘级增长。
03一步步，推导出优化思路
1
发现可以复用的信息
给每个节点维护当前已知最小距离 dist。
2
建立可维护的状态
非负边权保证：未确定节点中 dist 最小的节点，距离可以最终确定。
3
消除重复工作
用这个节点尝试松弛每条出边，再选择下一个最近节点。
贯穿算法的不变量
已确定节点的距离就是最短路；未确定节点记录目前已发现路径的最小代价。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Dijkstra交互演示
STEP 01 / 34无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01
源点为 0。其距离为 0，其余暂为无穷大。所有边权必须非负。
dijkstra.py参考实现 · 当前第 4 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
本课采用直观的线性选最小值：V 次选择，每次扫描 V 个节点，加上所有边的松弛。二叉堆版本可改善到 O((V+E)log V)。
辅助空间
dist、visited 和候选节点集合都是 O(V)，不含输入邻接表。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
不能处理负权
负权会破坏已确定距离不会变小的证明，应考虑 Bellman–Ford。
02
不可达不是 0
不可达节点距离保持为 ∞。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01Dijkstra 的关键前提？
02松弛是什么？
03本课线性选点版本的时间复杂度？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。