# 最短路径怎样一圈圈确定下来

By DUSK

Topic: Maths

[Open the interactive Jig](https://ask.jig.com/j/yJNvcUqBR0ag)

## Guide

### 1. 最短路径怎样一圈圈确定下来

六座街区塔是节点，连接它们的路是边，路边数字是权重，也就是走这条路的代价。起点 A 的距离是 0，其他点还不知道，先记成 ∞。

示意图：节点位置和权重都是虚构的，不是真实道路；路的长短不代表权重。

### 2. 松弛：写下暂定距离

从 A 出发，沿每条路算一算：A 的距离加上边权。B 得到 4，C 得到 2。这叫“松弛”：发现更短的走法，就改写暂定距离。

琥珀色数字是暂定距离，还可能变小；金色数字已经确定。

### 3. 优先选择：总距离最小的先确定

在所有暂定的点里，挑离起点总距离最小的 C（2），把它确定下来。再从 C 松弛：B 经过 C 只要 2\+1=3，比直走的 4 更短，于是改写。

比较的是从起点出发的总距离，不是“下一条边最短”。

### 4. 一步一步向外推进

每按一次，就确定一个总距离最小的点，并从它松弛邻居。金色波前按距离一圈圈展开，点被确定的顺序正是距离从小到大的顺序。点一座塔，可把它设为终点。

权重不能为负，否则已经确定的距离可能被推翻。

### 5. 边最少，不一定最短

从 A 到 F，只走 3 条路的路线 A→B→D→F 总长 15。Dijkstra 找到的金色路线要走 5 条路，总长却只有 13。

金色路线是顺着每个点的“前驱”从终点倒推回起点得到的。

### 6. 换个起点和终点

先选择“点选起点”或“点选终点”，再点一座塔。波前会从新起点重新展开，并亮出到终点的最短路线。要点：每次确定当前总距离最小的点，权重不为负，它的距离就不会再变。