基于map-reduce的并行最短路径算法 （转）

一个有向图，由（V，E）组成，其中V是顶点的集合，E为联结各顶点的边，每条边e可能有相应的权重w。

图的表示方式有两种：邻接矩阵和邻接表。其中对于节点数较少的图，用邻接矩阵表示较为方便，计算时也能充分应用矩阵计算的一些优势。但是当节点数特别大，需要借助map-reduce计算时，用邻接表是更为合适的选择。每一行数据，key为NodeId，值为与这个节点邻接的所有节点的AdjacentList（可能还包含了每一个节点的权重）。

有向图的最短路径，即从源点s出发，到达图上任意结点的最短路径。

图论中最经典的最短路径算法即Dijkstra算法，它采用了贪心的策略，利用宽度优先一层层搜索，直到遍历所有结点或已经找到最短路径。算法伪代码如下：

Dijkstra(G,w,s)

d[s]←0

forallvertexv∈Vdo

d[v]←∞

Q←{V}

whileQ!=∅do

u←ExtractMin(Q)

forallvertexv∈u.AdjacencyListdo

ifd[v]>d[u]+w(u,v)then

d[v]←d[u]+w(u,v)

以下图的例子来说明这个算法：

n1为起始点。首先标记它到自已的距离为0，然后算法把所有节点(n2~n5)加入到优先队列Q中，并标记n1到这些点的距离为∞。

进入循环：

第一次迭代，从Q中取出最近的扩张点n1，找到n1的邻接点n2,n3，并更新到n2,n3的距离分别为10和5。

第二次迭代，从Q中取出最近的扩张点n3，找到n3的邻接点n2,n5,n4，这时发现n1经n3到n2的距离比直接到n2的距离要短，于是更新到n2的距离为8，到n5的距离为7，到n4的距离为14。

第三次迭代，从Q中取出最近的扩张点n5...

当所有点都搜索过后，算法终止，此时已经找到n1到各点的最短距离。

Dijkstra算法关键的一点是优先队列Q（实际实现可以用数组），它保存了全局的从源点出发最近的结点。而map-reduce则无法做到这一点（其实也不是做不到，就是比较麻烦，需要用distributedcache）。

基于map-reduce的并行算法跟Dijkstra算法有点类似，它也基于Dijkstra的迭代思想，伪代码如下：

classMapper

methodMap(nidn,nodeN)

d←N.Distance

Emit(nidn,N)//Passalonggraphstructure[1]

forallnodeidm∈N.AdjacencyListdo

Emit(nidm,d+w)//Emitdistancestoreachablenodes[2]

classReducer

methodReduce(nidm,[d1,d2,...])

dmin←∞

M←∅

foralld∈counts[d1,d2,...]do

ifIsNode(d)then

M←d//Recovergraphstructure

elseifd<dminthen//Lookforshorterdistance

dmin←d

M.Distance←dmin//Updateshortestdistance

Emit(nidm,nodeM)

它每次迭代执行一个map-reducejob，并且只遍历一个节点。在Map中，它先输出这个节点的完整邻接节点数据，即[1]。然后遍历该节点的邻接节点，并输出该节点ID及权重。在Reduce中，对当前节点m，遍历map的输出权重，若比当前的路径值小，则更新。最后输出该节点的路径值及完整邻接节点数据，作为下一次迭代的输入。

实现上有个细节需要注意的是，map的输出有两种类型的数据：邻接节点数据和权重数据，这可以通过一个包装类，并设置一个dataType变量来实现。

当遍历完所有的节点之后，迭代就终止了。

这个实现还有一个小问题就是，不知道完整的最短路径，这可以在[2]中修改一下Map的输出来实现。

下面是一个例子，邻接节点的数据格式为：nodeId-->distance|adj1:w1,adj2:w2...

原始输入为：

n1-->0|n2:6,n3:15,n4:20

n2-->∞|n3:5,n4:8

n3-->∞|n4:2

n4->∞|

第一次迭代：

Map：

n1-->0|n2:6,n3:15,n4:20

n2-->∞|n3:5,n4:8

n3-->∞|n4:2

n4->∞|

n2-->6

n3-->15

n4-->20

Reduce：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->15|n4:2

n4-->20|

第二次迭代：

Map：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->15|n4:2

n4-->20|

n3-->11

n4-->14

Reduce：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->11|n4:2

n4-->14|

第三次迭代：

Map：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->11|n4:2

n4-->14|

n4-->13

Reduce：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->11|n4:2

n4-->13|

第四次迭代：

Map：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->11|n4:2

n4-->13|

Reduce：

n1-->0|n2:6,n3:15,n4:20

n2-->6|n3:5,n4:8

n3-->11|n4:2

n4-->13|

迭代终止