MapReduce实现单元最短路径算法.doc

格式约定： 用邻接表的方式来存储图，在文件中，每一行数据代表图的一个节点，行的格式可以采用一下格式：IDEdges其中ID代表节点的标识，Edges代表从某一节点出发的所有的边（对于有向图）Edges又可以用从该节点出发的边的另一端的节点表示。例如图1.1就可以用邻接表表示。 在求解图的问题时，图中的节点和边往往含有更多的信息，在用标色法求解单元最短路径时，节点的信息还包括节点的颜色、节点到源点的距离等，边的信息包括边的权值等。对以上邻接表作稍微改进便可满足要求。更新后的图文件的每一行的格式如下：IDdistancecolorEdges（weight）图1.1所示有向图加上权值信息后如图1.2所示，用邻接表表示如下其中MAX表示无穷大，颜色域，0：白色；1：灰色；2：黑色 算法流程：MAP: list() /k1：节点的ID；v1:该节点的距离、边、边的权值、颜色beginIf( color(k1) = = gray ) /如果k1的还需处理，即k1的颜色为灰色 ki p | (k1 ,ki) k1.Edges /对所有k1指向的节点If ( distance(k1) + weight(k1 ,ki) distance(ki) Set distance(distance(ki) = distance(k1) + weight(k1 ,ki); Set color(ki) = gray;emit (ki, v1)Set color(k1) = black;emit (k1, v1)endReduce BeginSet color(k2) = white;Set distance(k2) = MAX; vi list(v2)If( vi.color is hevier than k2)Set color(k2) = vi.color;If vi.distance distance(k2) )Set distance(k2) = vi.distance; If(vi.color = gray)Set color(k2) = gray; Set Edges(k2) = vi.edges if vi.edges != null; emit (k2, v) End Int I = 0;While (+i) inputPath = mapredJob(i).outPath outPath = createPath() Do mapredJob(i); If( canEnd)Break;运行示例： 一个job得输出作为另一个job的输入，多个job组成job chain 来完成最短路径的求算，当某一个job的输出中所有的节点中没有灰色节点时时停止迭代。算法停止。 Input10|1|2,10,4,5, 2MAX|0|3,1,4,2, 3MAX|0|5,4, 4MAX|0|5,2,3,9,2,3, 5MAX|0|3,6,1,7, After job_1Map :10|2|2,10,4,5, 210|1| 45|1| 2MAX|0|3,1,4,2, 3MAX|0|5,4, 4MAX|0|5,2,3,9,2,3, 5MAX|0|3,6,1,7, After job_1 Redeuce: 10|2|2,10,4,5,210|1|3,1,4,2,3MAX|0|5,4,45|1|5,2,3,9,2,3,5MAX|0|3,6,1,7,After job_2 Map :10|2|2,10,4,5,210|2|3,1,4,2,311|1|412|1|57|1|314|1|28|1|3MAX|0|5,4,45|2|5,2,3,9,2,3,5MAX|0|3,6,1,7,After job_2 Reduce:10|2|2,10,4,5,28|1|3,1,4,2,311|1|5,4,45|2|5,2,3,9,2,3,57|1|3,6,1,7,After job_3 Map:10|2|2,10,4,5,28|2|3,1,4,2,311|2|5,4,39|1|410|1|515|1|313|1|114|1|45|2|5,2,3,9,2,3,57|2|3,6,1,7,After job_3 Reduce :10|2|2,10,4,5,28|2|3,1,4,2,39|1|5,4,45|2|5,2,3,9,2,3,57|2|3,6,1,7,After job_4 Map:10|2|2,10,4,5,28|2|3,1,4,2,39|1|5,4,513|1|45|2|5,2,3,9,2,3,57|2|3,6,1,7,After job_4 Re