一句话版:找到与起点相邻最近点,再把这个点与源点看做一个整体,作为新的起点,重复步骤,直到抵达目标。
(示例如下)
本文参考视频:https://www.youtube.com/watch?v=pVfj6mxhdMw
使用两个数组,visited
& unvisited
表示访问与未访问的顶点。
假设要计算的图如下,目标是求 $A\to C$ 的最短距离:
A---6---B
| /|\
| / |
| / | \
1 2 2 C
| / | /
| / | /5
|/ |/
D---1---E
我们首先访问 A。可以得到下表:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A | 0 | null |
然后我们访问与 A 相邻的 B、D,可得下表:(注:A/
表示 A 已经访问过)
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | null |
B | 6 | A |
D | 1 | A |
然后对于 B、D,先看 B,与 B 相邻的有 C 和 D:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | 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/ | 0 | null |
B/ | 6 | A |
C | 5+6 | B |
D | 1 | A |
之后我们访问 D。与 D 相邻的有 B,E,而 B 访问过了,所以直接考虑 E:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | null |
B/ | 6 | A |
C | 5+6 | B |
D/ | 1 | A |
E | 1+1 | D |
然后考虑与 E 相邻的 D、B、C,其中只有 C 未尝访问。所以:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | null |
B/ | 6 | A |
C | 5+6 | B |
D/ | 1 | A |
E/ | 1+1 | D |
C | 2+5 | E |
可以发现又出现了两个 C,舍去距离 A 最远的,得到:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | null |
B/ | 6 | A |
D/ | 1 | A |
E/ | 1+1 | D |
C | 2+5 | E |
最后 C 标记为已访问:
顶点 | 到 A 的最短距离 | 访问的前一个顶点 |
---|---|---|
A/ | 0 | null |
B/ | 6 | A |
D/ | 1 | A |
E/ | 2 | D |
C/ | 7 | E |
从这个表,便可以知道 A、C 的最短距离是 7,路径(通过第三列回溯)是 $C\leftarrow E \leftarrow D \leftarrow A$。