Site Overlay

Dijkstra 寻路算法的工作原理(无废话)

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

(示例如下)

本文参考视频: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$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注