代码与动画 DIJKSTRA
Dijkstra 最短路径.
确定当前距离最小的节点，再松弛它的出边。
时间 O(V² + E)空间 O(V)非负权有向图
原理与执行逻辑
维护起点到每个节点的当前最短估计，每次确定未处理节点中距离最小者，再用它的出边改进其他节点的估计。
执行步骤
- 将起点距离设为 0，其余节点距离设为 ∞。
- 线性选择尚未确定且距离最小的节点。
- 对它的每条出边比较 dist[u] + weight 与 dist[v]，更小时更新。
- 重复选择与松弛；剩余距离全为 ∞ 时停止。
关键理解
非负边权保证被选中的最小距离无法经由后续节点变得更短。当前实现使用线性选择，输入负权边会破坏这个前提。
简短示例
A→B 为 5，A→C 为 2，C→B 为 1。先确定 C 的距离 2，再把 B 的估计从 5 更新为 3。
代码与执行动画
STEP 0 / 20function dijkstra(graph, start) { const dist = Object.fromEntries(Object.keys(graph).map(v => [v, Infinity])); const done = new Set(); dist[start] = 0; while (done.size < Object.keys(graph).length) { let node = null; for (const v of Object.keys(graph)) { if (!done.has(v) && (node === null || dist[v] < dist[node])) node = v; } if (node === null || dist[node] === Infinity) break; done.add(node); for (const [next, weight] of graph[node]) { if (dist[next] > dist[node] + weight) dist[next] = dist[node] + weight; } } return dist;}当前数据正在操作已访问 / 命中标记 / 指针
0
初始化距离
起点 A 距离为 0，其余为 ∞。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
Dijkstra 最短路径的操作规则
本实现线性扫描未确定节点，不使用优先队列。顶点固定 A–F，支持权重 0；不可达节点的距离为 ∞。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目743. 网络延迟时间打开题目
非负权有向图的单源最短路径；答案为所有可达距离的最大值。