Dijkstra 算法及正确性分析

Max 的个人博客 / 2355 / 2 / 创建于 6年前 / 更新于 5年前

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

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

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

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

found集合

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

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

dist集合

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

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

初始一下dist集合

const MAX = 65525; //65525是我们定义的一个不可能出现的大值

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

算法描述

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

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

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

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

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

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

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

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

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

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

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

dist集合更新如下

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

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

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

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

更新后的found和dist如下

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

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

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

更新后的s和dist如下

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

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

再次循环↓

更新后的found和dist如下

$s = ['宝安中心', '深圳北站', '新安', '福田', '购物公园'];

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

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

算法描述完毕!

算法实现

https://github.com/weiwenhao/algorithm/blo...

正确性分析

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

$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-购物公园 < 宝安中心-福田-购物公园是否能够成立呢？假如等式不成立，则说明不可能存在一条比宝安中心-福田-购物公园更短的全局最短路径。

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

正确性分析完毕！