Dijkstra非负加权有向图最短路径算法

成果在这里,前天完成的,花了大约半天的时间。参考资料主要是维基百科一篇博客

在分析自己代码前,先写一点自己对于Dijkstra算法的理解。

假定上午的s, u, v分别是某个非负加权有向图的顶点,要求从s到v的最短路径。定义d(x)为从s到x定点的最短路径距离,则到v顶点的最短路径据路即是d(v)。同时定义从顶点x到顶点y的权值为w(x, y),假如存在从x到y的一条有向边,则w(x, y)即这条边的权值,否则w(x, y)无意义,或者说是无穷大。
Dijkstra算法认为:假如存在从u到v的一条有向边,并且d(u) + w(u, v) < d(v),则认为到v顶点最短路径经过u顶点。为了计算方法,可以认为d(v)原先为无穷大,实际计算的是所有到达点是v的u中最小的u。 单独看上述的理论时,个人理解为计算v到s的最短路径应该是一个回溯,更确切的讲应该是DP。但是Dijkstra算法实际为广度搜索,可以计算所有顶点的最短路径。我的目的是学习这个经典算法,所以就按照算法的步骤来。 以下是来自维基百科的伪代码

老实说单独看这段伪代码不太好理解算法步骤,所以我又看了博客中的算法步骤图后才大致理解了。不过实际实现时还是遇到了一些问题,还是先从伪代码讲起。

伪代码中首先是初始化,设置所有d(x)为无穷大,先忽略路径回溯用的顶点数组previous,无穷大我实际设置为Integer.MAX_VALUE。
接下来是设置d(s) = 0,这个很好理解,从起点到起点的最短距离肯定是0。
S和Q是两个集合,分别保存已经访问过的顶点和未访问过的顶点。
extract_min是算法的重点之一,维基百科中的说明是取得d(x)最小的顶点。比如第一步时d(s)为0,其他d(x)都为无穷大,所以毫无疑问第一次u肯定为s。
接下来取得邻接u的顶点v集合,设置d(v),思路和之前我理解的Dijkstra算法的思想类似。实际d(v)一开始为无穷大,根据边拓展得到可用的路径和相应的路径。这里会有一个疑问,拓展得到的d(v)肯定是最短的么?严格来说是不保证的,考虑如下情况:

存在邻接表: s -> v0, w0; s -> v1, w1; v1-> v0, w10
一开始从s的拓展会更新d(v0) = w0,d(v1) = w1。因为从v0的拓展不会更新d(v0)本身,如果w0 > w1 + w10,即实际d(v0)应该为w1 + w10,那么算法就应该是错的。实际中算法还会拓展v1,比较d(v0) 和 d(v1) + w10的关系,如果比较了就可以得到正确的最短路径。但是拓展v0和v1存在先后关系,假设先拓展v0,算法就会出问题。于是焦点就变为extract_min步骤,如果先拓展v0,那么算法就有问题。但是w0 > w1 + w10 并且w为非负数 => w0 > w1 => d(v0) > d(v1) => extract_min(q) 结果为v1,即实际不会先拓展v0。换句话说,一次替换d(v)不会得到最小值,但和extract_min一起保证能取到最小值。

从上面的伪代码翻译为实际代码主要关注两部分:第一部分是图的表示,我选用邻接表,第二部分是综合extract_min, d[v]获取和修改的顶点距离。
针对上述伪代码的邻接表接口定义为:

两个函数分别针对while中for的数据来源和w(u, v)。内部使用哈希表,保存映射(start vector) -> (end vector, weight)。具体代码如下,输入为(u, v, w)的有向边和权值的表示方法:

顶点距离相对难实现一些,伪代码中需要的功能是:

个人理解为最小堆移除功能,又要随机访问功能。其次,理论上移除后顶点到了另外一个集合,但是设置距离要跨越集合。感觉是一个很纠结的数据结构?简单起见,我就用数组实现。同时,为了区分顶点是否访问过,我增加了accessed属性。

设计好这两个主要部分之后,原先的伪代码可以转化为:

上述代码有一个之前未提到的点,Dijkstra虽然能获取到所有点的最短距离,但是有时候我们只需要指定两点就行,所以在extract_min是指定的目标顶点时,就可以跳出。(来自维基百科的提示)
测试代码

除了获取最短路径距离之外,如何记录最短路径也是需要考虑的。因为最短路径距离肯定关联一个前向点,每个前向点的最短距离下也肯定有前向点。所以代码中只要记录每个最短路径距离时的前向点即可。即上述代码中的previousLink。相应的,恢复路径需要回溯这个前向数组。

这里使用了栈来回溯,如果两点之间不连接的话,在findMinDistance中就已经停止了,不会再尝试恢复最短路径。

最后,小结一下个人感受:Dijkstra是一个涉及多种数据结构的算法,想要完全了解他个人还需要进一步深化数据结构的认识。