一句话版**:找到与起点相邻最近点,再把这个点与源点看做一个整体,作为新的起点,重复步骤,直到抵达目标。**

(示例如下)

本文参考视频:https://www.youtube.com/watch?v=pVfj6mxhdMw

使用两个数组,visited & unvisited 表示访问与未访问的顶点。

假设要计算的图如下,目标是求 $A\to C$ 的最短距离:

|      /|\
|     / | \5
|    /  |  \
1   2   2   C
|  /    |  /
| /     | /5
|/      |/
D---1---E```

我们首先访问 A。可以得到下表:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A  |           | null     |

然后我们访问与 A 相邻的 B、D,可得下表:(注:`A/` 表示 A 已经访问过)

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B  | 6         | A        |
| D  | 1         | A        |

然后对于 B、D,先看 B,与 B 相邻的有 C 和 D:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| C  | 5+6       | B        |
| D  | 2+6       | B        |
| D  | 1         | A        |

这里我们发现 D 出现了两次,一次是 BD+BA = 2 + 6 = 8,一次是 DA = 1,而 $1 < 8$ 所以舍弃前一种:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| C  | 5+6       | B        |
| D  | 1         | A        |

之后我们访问 D。与 D 相邻的有 B,E,而 B 访问过了,所以直接考虑 E:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| C  | 5+6       | B        |
| D/ | 1         | A        |
| E  | 1+1       | D        |

然后考虑与 E 相邻的 D、B、C,其中只有 C 未尝访问。所以:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| C  | 5+6       | B        |
| D/ | 1         | A        |
| E/ | 1+1       | D        |
| C  | 2+5       | E        |

可以发现又出现了两个 C,舍去距离 A 最远的,得到:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| D/ | 1         | A        |
| E/ | 1+1       | D        |
| C  | 2+5       | E        |

最后 C 标记为已访问:

| 顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
| -- | --------- | -------- |
| A/ |           | null     |
| B/ | 6         | A        |
| D/ | 1         | A        |
| E/ | 2         | D        |
| C/ | 7         | E        |

从这个表,便可以知道 A、C 的最短距离是 7,路径(通过第三列回溯)是 $C\\leftarrow E \\leftarrow D \\leftarrow A$。