基于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|
迭代终止