mapreduce实现单元最短路径算法

《mapreduce实现单元最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、格式约定：用邻接表的方式来存储图，在文件中，每一行数据代表图的一个节点，行的格式可以采用一下格式：IDEdges其中ID代表节点的标识，Edges代表从某一节点出发的所有的边（对于有向图）Edges又可以用从该节点出发的边的另一端的节点表示。例如图1.1就可以用邻接表表示。在求解图的问题时，图中的节点和边往往含有更多的信息，在用标色法求解单元最短路径时，节点的信息还包括节点的颜色、节点到源点的距离等，边的信息包括边的权值等。对以上邻接表作稍微改进便可满足要求。更新后的图文件的每一行的格式如下：IDdistancecolorEdges（weight）图1.1所示有向图加上权值信息后如图1

2、.2所示，用邻接表表示如下其中MAX表示无穷大，颜色域，0：白色；1：灰色；2：黑色算法流程：MAP:àlist()//k1：节点的ID；v1:该节点的距离、边、边的权值、颜色beginIf(color(k1)==gray)//如果k1的还需处理，即k1的颜色为灰色{"kiÎ{p

3、(k1,ki)Îk1.Edges}//对所有k1指向的节点If(distance(k1)+weight(k1,ki)

4、ay;emit(ki,v1)}Setcolor(k1)=black;}emit(k1,v1)endReduceàBeginSetcolor(k2)=white;Setdistance(k2)=MAX;"viÎlist(v2)If(vi.colorishevierthank2){Setcolor(k2)=vi.color;}If{vi.distance

5、sifvi.edges!=null;emit(k2,v)EndIntI=0;While(++i){inputPath=mapredJob(i).outPathoutPath=createPath()DomapredJob(i);If(canEnd){Break;}}运行示例：一个job得输出作为另一个job的输入，多个job组成jobchain来完成最短路径的求算，当某一个job的输出中所有的节点中没有灰色节点时时停止迭代。算法停止。Input10

6、1

7、2,10,4,5,2MAX

8、0

9、3,1,4,2,3MAX

10、0

11、5,4,4MAX

12、0

13、5,2,3,9,2,3,5MAX

14、0

15、3,6,1,

16、7,Afterjob_1Map:10

17、2

18、2,10,4,5,210

19、1

20、45

21、1

22、2MAX

23、0

24、3,1,4,2,3MAX

25、0

26、5,4,4MAX

27、0

28、5,2,3,9,2,3,5MAX

29、0

30、3,6,1,7,Afterjob_1Redeuce:10

31、2

32、2,10,4,5,210

33、1

34、3,1,4,2,3MAX

35、0

36、5,4,45

37、1

38、5,2,3,9,2,3,5MAX

39、0

40、3,6,1,7,Afterjob_2Map:10

41、2

42、2,10,4,5,210

43、2

44、3,1,4,2,311

45、1

46、412

47、1

48、57

49、1

50、314

51、1

52、28

53、1

54、3MAX

55、0

56、5,4,45

57、2

58、5,2,3,9,2,3,5MAX

59、0

60、3

61、,6,1,7,Afterjob_2Reduce:10

62、2

63、2,10,4,5,28

64、1

65、3,1,4,2,311

66、1

67、5,4,45

68、2

69、5,2,3,9,2,3,57

70、1

71、3,6,1,7,Afterjob_3Map:10

72、2

73、2,10,4,5,28

74、2

75、3,1,4,2,311

76、2

77、5,4,39

78、1

79、410

80、1

81、515

82、1

83、313

84、1

85、114

86、1

87、45

88、2

89、5,2,3,9,2,3,57

90、2

91、3,6,1,7,Afterjob_3Reduce:10

92、2

93、2,10,4,5,28

94、2

95、3,1,4,2,39

96、1

97、5,4,45

98、2

99、5,2,3,9,2,3,57

100、2

101、3,6,1,7,Afterjob_4Ma

102、p:10

103、2

104、2,10,4,5,28

105、2

106、3,1,4,2,39

107、1

108、5,4,513

109、1

110、45

111、2

112、5,2,3,9,2,3,57

113、2

114、3,6,1,7,Afterjob_4Reduce:10

115、2

116、2,10,4,5,28

117、2

118、3,1,4,2,39

119、2

120、5,4,45

121、2

122、5,2,3,9,2,3,57

123、2

124、3,6,1,7,Nonode’scolorisgray(1)end.