当前位置:首页 > 开发 > 行业应用 > 正文

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

发表于: 2012-08-16   作者:缥缈孤鸿   来源:转载   浏览:
摘要: 一个有向图,由(V,E)组成,其中V是顶点的集合,E为联结各顶点的边,每条边e可能有相应的权重w。 图的表示方式有两种:邻接矩阵和邻接表。其中对于节点数较少的图,用邻接矩阵表示较为方便,计算时也能充分应用矩阵计算的一些优势。但是当节点数特别大,需要借助map-reduce计算时,用邻接表是更为合适的选择。每一行数据,key为NodeId,值为与这个节点邻接的所有节点的AdjacentList
一个有向图,由(V,E)组成,其中V是顶点的集合,E为联结各顶点的边,每条边e可能有相应的权重w。

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


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

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

Dijkstra(G,w, s)
    d[s] ← 0
    for all vertex v ∈ V do
        d[v] ← ∞
    Q ← {V }
    while Q != ∅ do
        u ←ExtractMin(Q)
        for all vertex v ∈ u.AdjacencyList do
            if d[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则无法做到这一点(其实也不是做不到,就是比较麻烦,需要用distributed cache)。




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

class Mapper
    method Map(nid n, node N)
    d ← N.Distance
    Emit(nid n,N)                                  //Pass along graph structure [1]
    for all nodeid m ∈ N.AdjacencyList do
        Emit(nid m, d+w)                          //Emit distances to reachable nodes [2]

class Reducer
    method Reduce(nid m, [d1, d2, . . .])
    dmin←∞
    M ← ∅
    for all d ∈ counts [d1, d2, . . .] do
        if IsNode(d) then
            M ← d                                       //Recover graph structure
        else if d < dmin then                  //Look for shorter distance
            dmin ← d
    M.Distance← dmin                        //Update shortest distance
    Emit(nid m, node M)

它每次迭代执行一个map-reduce job,并且只遍历一个节点。在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 |

迭代终止


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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号