最近朋友问了一个关于列车调度的问题,求两个地点之间的最短路径。听起来挺简单的问题,可是仔细思考后发现完全无从下手。最近空闲下来便恶补了一番数据结构。

求最短路径的方法有Dijkstra,Floyd,BFS等等 其中Floyd适合多源最短路径,BFS适合无权值的情况,这里问题属于单源最短路径,所以我们采用Dijkstra算法.

开干吧!拿出地铁卡就是一顿画,现在我们就把问题抽象为求宝安中心-老街的最短路径

开始之前首先我们介绍几个概念

found集合

对于这种起点到某个顶点的真正的最短路径,我们称它为全局最短路径。已经找到全局最短路径的顶点,我们将其储在found集合中.现在来初始化一下found

1
2
// 初始时,我们已知的就只有宝安中心到宝安中心的最短路径
$found = ['宝安中心'];

dist集合

用来存储起点(宝安中心)到某个顶点u, 相对于S的最短路径。通俗解释就是:宝安中心到世界之窗经过了新安,那么必须有新安∈ S。 否则我们无法直接知道其相对最短路径,在dist中则将其记为不可能存在的大值,用来表示这个点我们目前还没有办法探索到。

dist中存储的最短路径称之为相对于S的最短路径。下文我们简称为相对最短路径,和其对应的我们有一个全局最短路径

初始一下dist集合

1
2
3
4
5
6
7
8
9
10
11
const MAX = 65525; //65525是我们定义的一个不可能出现的大值

$dist = [
'深圳北站' => 5,
'新安' => 8,
'世界之窗' => MAX,
'福田' => MAX,
'购物公园' => MAX,
'老街' => MAX,
'布吉' => MAX,
];

算法描述

开始我们的算法~ 我们首先找到dist中的最小值,这里是 深圳北站 => 5

顺便告诉你一个激动人心的消息,我们找到了宝安中心到深圳北站的全局最短路径。

what?为什么dist中的最小值就是我们要找的全局最短路径(这里是宝安中心-深圳北站)?
我们要找的不是宝安中心-老街的全局最短路径吗,知道了宝安中心-深圳北站的最短路径有什么用吗?
我现在没法给你一个很好的解释,我们继续往下看。

继续进行算法,下面是红色顶点表示已经确定了全局最短路径的顶点


既然已经又找到了一个全局最短路径顶点,我们就把它更新到found集合中

1
$found = ['宝安中心', '深圳北站'];

集合found中的元素增加了一枚后,我们的视野变的宽广了。我们可以通过深圳北站作为一个中转更新 dist这个相对最短路径集合了

通过深圳北站这个中转站我们可以得到已下相对最短路径

宝安中心-深圳北站-新安 = 5 + 2 = 7
宝安中心-深圳北站-福田 = 5 + 5 = 10
宝安中心-深圳北站-布吉 = 5 + 10 = 15

现在可以马上去替换我们dist集合中的值了吗?别急,我们需要的是相对最短路径,可不是什么阿猫阿狗就能进来的。所以我们需要进行一个比较.

1
2
3
4
// 如果新的相对最短路径比原有的相对最短路径要小,我们则进行一个更新
if ($newWeight < $dist['新安']) {
$dist['新安'] = $newWeight;
}

dist集合更新如下

1
2
3
4
5
6
7
8
9
$dist = [
'深圳北站' => 5, // ok
'新安' => 7, //8 -> 7
'世界之窗' => MAX,
'福田' => 10, // MAX -> 10
'购物公园' => MAX,
'老街' => MAX,
'布吉' => 15 // MAX -> 15
];

现在我们重复之前的步骤,找一个最小值,其就是我们下一个全局最短路径。要记住,深圳北站就不要加入查找队列了,其已经被found了

人眼扫描后可以确定下一个全局最短路径的顶点为新安。并且有了新安的中转,我们可以再次拓宽我们的视野

为了表示清晰,对于还没有探索到相对最短路径,先隐藏其权重值


更新后的founddist如下

1
2
3
4
5
6
7
8
9
10
11
$found = ['宝安中心', '深圳北站','新安'];

$dist = [
'深圳北站' => 5, // ok
'新安' => 7, // ok
'世界之窗' => 16, // MAX -> 16 = 9+7 = 宝安->新安 + 新安->世界之窗
'福田' => 10, // MAX -> 10
'购物公园' => MAX,
'老街' => MAX,
'布吉' => 15
];

再次循环 (目标已经出现在我们的视野中啦,别着急,我们还没有确定其全局最短路径) ↓

更新后的s和dist如下

1
2
3
4
5
6
7
8
9
10
11
$found = ['宝安中心', '深圳北站', '新安', '福田'];

$dist = [
'深圳北站' => 5, // ok
'新安' => 7, // ok
'世界之窗' => 16,
'福田' => 10, // ok
'购物公园' => 12, // MAX -> 12
'老街' => 15, // MAX -> 15
'布吉' => 15
];

再次循环↓

更新后的found和dist如下

1
2
3
4
5
6
7
8
9
10
11
$s = ['宝安中心', '深圳北站', '新安', '福田', '购物公园'];

$dist = [
'深圳北站' => 5, // ok
'新安' => 7, // ok
'世界之窗' => 16,
'福田' => 10, // ok
'购物公园' => 12, // ok
'老街' => 15,
'布吉' => 15
];

再次寻找dist中最小值时, 找到了我们的目标,老街。

算法描述完毕!

算法实现

https://github.com/weiwenhao/algorithm/blob/master/src/Dijkstra.php

正确性分析

为什么dist集合中的最小值就是我们要找的全局最短路径?

1
2
3
4
5
$dist = [
'福田' => 10, // ok
'购物公园' => 12,
'老街' => 15,
];

以某一次dist集合的部分数据为例子,按照算法描述 宝安中心-福田-购物公园是我们要找的全局最短路径。现在我们假设到宝安中心-购物公园存在更短的路径,则存在如下两种情况

情况1

红色区域代表集合found,表示已经找到了全局最短路径的顶点集合。
上面提到过,dist集合中存储的是相对于S的最短路径。

对于这种情况,算法在进行dist集合更新操作的时候就已经判断了宝安中心-福田-购物公园宝安中心-X-购物公园之间的更小值,因此这种情况不可能存在。我们继续来看另外一种更加可能出现的情况

  • 情况2

是否会存在这样一条最短路径呢?因为y-购物公园的距离我们并没有探索过,所以这种情况是需要慎重思考一种情况。

先让时光倒流

此时我们的dist集合中一共有5个顶点。其中宝安中心,福田,X已经被加入到了found集合中。Y通过X的中转后被发现,购物公园通过福田中专后被发现。
此时根据我们的算法,将会在Y和购物公园中选取一个最小值,作为下一个全局最短路径顶点。这里算法选择了购物公园。说明宝安中心-福田-购物公园 < 宝安中心-X-Y

回到情况2

在有了 宝安中心-福田-购物公园 < 宝安中心-X-Y前提下。
宝安中心-X-Y-购物公园 < 宝安中心-福田-购物公园是否能够成立呢?假如等式不成立,则说明不可能存在一条比宝安中心-福田-购物公园更短的全局最短路径。

等式是否成立我相信你一目了然。

正确性分析完毕!

结语

你可能还在惊讶于dijkstra算法为什么这么神奇?就算我们已经知道了算法步骤,分析了算法的正确性。可还是不禁会感叹,到底是怎么做到的,到底是怎么找到最优解的?

回过头去看看算法描述你会发现,其实dijkstra并不知道自己什么时候能够找到自己想要的目标,它只是关注于眼前的最优解,然后碰巧在某一时刻眼前的最优解就是要寻找的目标值。这看起来有点笨,但是在某些情况十分有用,比如路由寻址中查找最短路径必须要用到这种策略。

哦~对了,这种只关注于眼前最优解的方法其实有个更加有逼格的名字 —— 贪心算法。