每周学点大数据 | No.45 基于路径的图算法

No.45期

基于路径的图算法

Mr. 王：接下来我们看一类具体的问题，这类问题叫作基于路径的图算法。这类算法的目标是计算节点间关于路径的信息。在这类问题中，图中的边一般是加权的，这些权也可以叫作边的标记，包括代价、距离、或者相似性等。

小可：边的标记就像社交网络图里面的联系亲密度一样吧。

Mr. 王：是的。这类问题的典型例子就是单源最短路径、最小生成树、Steiner 树、拓扑排序等。

小可：Steiner 树我没有听说过，它是做什么用的呢？

Mr. 王：Steiner 树是连接给定集合的最小代价树，后面会再提到它的。这里我们要考虑的核心问题就是，如何将这些算法并行化，以解决对比较大的图的操作算法。

现在我用单源最短路径作为例子来说明如何发现计算过程中的并行化。

解决这个问题的经典算法是Dijkstra 算法。我们先来看看Dijkstra 算法在内存中的版本和思想。

Dijkstra 算法是由图灵奖获得者、荷兰人Dijkstra 提出的，是一个非常经典的求解单源最短路径的算法。它求解的问题是这样定义的：在一个加权有向图G=(V,E) 中，每一条边都有一个非负实数作为它的权，在图中我们标定一个源点u，去求解u 到图中其他所有顶点的最短距离，也就是最短路径的长度。

小可：这个算法还是非常实用的啊，如果将城市之间的交通抽象成一个图的话，那么通过

单源最短路径就能求解出一个城市到其他城市的最短距离。

Mr. 王：我们先给出这个算法的伪代码，然后再做解释。它的输入是图G、起始点u 和总节点数n。

Dijkstra(G,u,n)

{

将u 加入到集合S 中 ①

对于G 中的每一个节点n，将u 到n 的最短距离SP[n] 设为u 与n 设为邻接矩阵A[u][n] 中的值 ②

循环执行n-1 次 ③

{

从图G 的V-S 中选出一个SP[i] 最小的顶点i，将其加入到S 中 ④

对于V-S 中的每一个顶点j

{

SP[j] = min (SP[j],SP[i]+A[i][j]) ⑤

}

}

}

我们来分析一下这个算法。

①处：将初始节点u 加入到集合S 中。此处的集合S 表示的是我们已经访问过的节点，在算法开始时，仅有初始节点被访问过。

②处：这是一个初始化操作，将最短距离先设为源点直接可以到达的顶点的边的长度。至于不可达的那些顶点，则设为邻接矩阵中的值∞，它不会对后面的较小值比较造成任何影响。

③处：由于除了u 之外，还有n-1 个顶点，所以一共要执行n-1 次。

④处：开始对还没有被访问过的顶点（V-S 中的那些顶点）进行访问，要选择目前距离它比较近的那些顶点，因为它们更倾向于帮助发现更近的路径，所以我们是按照距离从小到大的顺序来选择顶点的。

⑤处：当引入了节点i 之后，我们要看它的引入是不是引起了更短距离路径的发现，所以要比较先经过I，再由(i,j) 这条边抵达j 的路径是不是比当前认为的到j 的最短距离更短一些，如果是，则说明i 的引入帮助发现了一条更短的路径，我们就更新到j 的最短距离；否则，维持原来的最短路径值即可。

循环结束时，SP[j] 中的值就是源点u 到j 的最短距离。

小可：还是挺好理解的，而且设计得非常巧妙啊。

Mr. 王：想想看，这个算法的时间复杂度如何？

小可：假设图中有n 个顶点，这个算法有两层循环：外层循环需要执行n-1 次；内层循环的执行是节点数目的线性函数，所以内层循环为O(n)。综合起来，两层循环就是O(n2)。

Mr. 王：不过你只说对了一半。当我们使用邻接矩阵表示一个图时，它的时间复杂度是O(n2) ；但如果图比较稀疏，边数非常少的话，则还可以尝试用邻接表来表示这个有向图。此时，内循环可以稍作修改，针对边去进行访问，沿着与i 相关的邻接表进行访问，这样算来，运行的时间与跟i 相关的边数相关，所有节点的边合成起来就会和图的边数呈线性关系，也就是O(e)。

小可：哦，原来还有这样的考虑。以后在研究图算法的复杂度时，要多考虑图的稀疏与稠密，还有图的实际存储结构，这些都会对算法的复杂度产生影响。

Mr. 王：内存版本的Dijkstra 算法每次沿着一个中间节点遍历图，基于总路径的长度去定义遍历的优先级。相当于在这一过程中我们建立一个堆，每次取出堆顶进行处理。在这里面就没有发现并行机制，因为我们每次处理的都是所维护的这个堆的堆顶，每次都在对一个新的顶点进行操作。

为了提升计算效率，我们就要尝试去挖掘其中可能并行的地方。可以想到，从源点出发，能不能不必每次只处理一个顶点，而是每次同时处理一个跳数的节点。比如，第一次处理从源点出发的1 跳节点，第二次可以从这些1 跳节点出发，去发现那些距离源点2 跳的节点，而这些工作之间并不会产生干扰。这样思考的好处在于，我们能够借此发现其中潜在的并行性。并行性在于在下一步开始之前，我们对本轮的这些节点的访问是可以并行进行的。

在传统的算法中，对于Dijkstra 算法仔细考察每个u，在其维护的堆中找到堆顶，从而可以安全地删除确定顶点。这部分内容前面已经提到过了，现在要考虑的就是在MapReduce 中，我们怎么去寻找其中潜在的并行性。

 对每个v 考察所有潜在的u。

 通过保存u 的前沿集合迭代计算（距离源点i 条边）。

小可：那么在MapReduce 中，具体是怎么做的呢？

Mr. 王：先来想想，要建立一个MapReduce 解决方案，首先要定义什么？

小可：我想应该是要定义出key-value 对吧。

Mr. 王：很好。在这个问题中，key-value 对是这样定义的：一个顶点的编号ID 是它的key，而value 包含< ∞ , -, {<succ-node-ID,edge-cost>}> 这样几个部分

 第一个数据域表示从源点到节点ID 的最短路径长度为∞。

 第二个数据域表示最短路径上的下一个节点。

小可：嗯，这个时候，最短路径多长还不知道，下一个节点也不知道，这里都初始化成无穷和空。

Mr. 王：succ-node-ID，是其邻居节点的ID，edge-cost 是到其邻居节点的路径长度。这两部分其实就是节点ID 的邻接表。

好了，接下来应该做什么？

小可：接下来就要定义Map 和Reduce 了。

Mr. 王：嗯，掌握这种解决问题的思维方式，与理解算法是同等重要的。

在Map 中，每一个Mapper 接收到的输入都是ID 作为key,<dist,next,{<succ-node-ID,edgecost>}>作为value 这样的key-value 对。但是对于每一个ID 对应的succ-node-ID，我们传送succ-node-ID 作为key，而{<node ID,distance+edge-cost>} 作为value 的key-value 对。这一步实际上是在做从源点到新发现的这个succ-node-ID 的路径和路径长度计算。

小可：这时我们是不是应该把最小的代价提取出来呢？

Mr. 王：不，这里并不需要把最短的路径提取出来，但是我们知道，最终要找的最短路径一定包含在这里面。即使提前找出这些最短的路径，也并不一定是最终的最短路径的一部分。

但是仅仅传送这个还是不够的，我们依然需要传送ID,distance,{<succ-node-ID,edge-cost>}这个key-value 对。想想看这是为什么？

小可：如果还需要传送这部分，则是因为在下一轮的迭代过程中还需要用到这些节点的原始数据。因为每一轮的迭代都和第一轮所做的计算并无本质区别，在计算下一轮的过程中，所使用的算法和第一轮也是一样的，依然是依赖如同第一轮那样的输入。

Mr. 王：很好。

小可：可是这样传送，到了最后节点ID 和其succ-node-ID 不是就都混到一起了吗？

Mr. 王：嗯，是这样，因为在Reduce 中，我们也确实需要这样的机制。

在Reduce 之前，我们会根据ID 做一个Group，也就是将相同的ID 聚集到一起，然后进入Reduce，将相同IDdistance 定义为前驱节点中的最小代价，而next 定义为具有最小代价的那个前驱节点。最后将这样的key-value 对传送出去，也就是传送ID<distance( 最小),next( 最小),{<succ-node-ID,edge-cost>}> 这种模式。

小可：嗯，似乎是懂了。

Mr. 王：哈哈，“似乎”可不行啊，我们举个例子，把这个问题彻底搞清楚。

这是一个典型的最短路径问题。

在第一轮迭代中，Mapper 传送出去的数据是(a,<s,10>) (c,<s,5>)，a 和c 分别是s 的后继节点，s 是源点，5 和10 是边的权重。

在Reducer 中，我们求出了到a 和c 的当前最短路径10 和5，按照之前我们定义的那种表示法，Reducer 会发送(a,<10, ...>) (c,<5, ...>) 这样的数据。

接下来是第二轮迭代。

Mapper ：(a,<s,10>) (c,<s,5>) (a,<c,8>) (c,<a,9>) (b,<a,11>) (b,<c,14>) (d,<c,7>)

Reducer ：(a,<8, ...>) (c,<5, ...>) (b,<11, ...>) (d,<7, ...>)

在第二轮迭代中，我们重启一次MapReduce，注意看新增的数据记录，(a,<c,8>) 这条记录表示，这一次发展到a 节点的邻居是c，而之前到c 的最短路径是5，a 到c 的距离是3，所以加起来s 到a 的当前最短路径就是8。

小可：相应的，(b,<a,11>) 表示发展到b 节点的邻居是a，原来到a 的最短路径是10，又因为a 到b 的距离是1，所以当前s 到b 的最短路径就是11。

Mr. 王：很好，其他的也是这个道理。接下来在Reducer 中，我们对这些键值对进行基于key 的分组，这样就能求出到当前这一轮迭代中各个可达节点的最短路径。第三轮迭代还是同样的道理。在这一轮迭代中，b、d 两个节点如同上一轮迭代被加入了研究范围，使用和上一轮迭代同样的方法解出了当前到达每个节点的最短路径长度。

Mapper ：(a,<s,10>) (c,<s,5>) (a,<c,8>) (c,<a,9>) (b,<a,11>) (b,<c,14>) (d,<c,7>) (b,<d,13>)(d,<b,15>)

Reducer ：(a,<8>) (c,<5>) (b,<11>) (d,<7>)

这时我们还要进行一轮迭代，发现第四轮迭代和第三轮迭代的结果已经完全一致，于是认为整个算法已经收敛了，无须继续进行下去，也就得出了从s 出发到每一个节点的最短路径。

内容来源：灯塔大数据 文章编辑：柯一