最快的路线是怎么算出来的？一张小地图看懂 Dijkstra 算法

图论 · 单源最短路径

3

7

2

5

2

3

2

4

家

超市

公园

医院

学校

车站

最快 10 分钟

最快的路线，

是怎么算出来的？

一张小地图，看懂迪杰斯特拉（Dijkstra）算法

先看地图

把城市画成点和线

问题

从家出发，最快要多久？

直觉会骗人

看着近的路，不一定快

换个思路

在家里打开水龙头

关键

水先到的时刻 ＝ 最短时间

迪杰斯特拉算法

不用真的放水，

重复两个动作就行

1

锁定没锁定的地点里，

挑数字最小的

739

2

更新走这边更快，

就把邻居的数字改小

7→5

一直重复，直到所有地点都锁定

准备

每个地点，发一张纸条

第 1 轮共 6 轮

锁定家，更新它的邻居

第 2 轮锁定

没锁定的里面，谁最小？

第 2 轮更新

经过超市，会不会更快？

第 3 轮共 6 轮

锁定公园，更新邻居

第 4 轮共 6 轮

锁定医院，更新邻居

第 5 轮共 6 轮

锁定学校，更新邻居

第 6 轮共 6 轮

锁定车站，全部完成

结果

想知道怎么走？往回找

一点历史

1956年

Edsger W. Dijkstra迪杰斯特拉 · 荷兰计算机科学家

在咖啡馆里

大约 20 分钟

今天还在用

地图导航

网络传输

游戏寻路

记住这两步

1锁定最近的

2更新它的邻居

前提路上的数字不能是负数

Dijkstra 算法 · 单源最短路径