4.1 Hadoop-dijkstra(狄克斯特拉)算法-计算最短距离

我会带着你远行 2022-05-24 07:23 215阅读 0赞

dijkstra(狄克斯特拉)算法： 从一个顶点到其余各顶点的 [最短路径][Link 1] 算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，常用在地图和社交

![20180523102851223][]

–步骤：

–A为起始点。首先标记它到自已的距离为0。到其他节点的距离为无穷大

–进入迭代：

•第一次迭代，从数据中取出起点A，找到A的邻接点B, C..，并更新到B, C的距离。

•第二次迭代，分别从扩张点B，C，G找到与他们相邻的点，这时发现A经C到G的距离比直接到G的距离要短，于是更新到G的距离为11，以此类推。

•一直所有点都有一个最短距离。而不是无穷大。结束迭代。

![20180523102858414][]

工程结构：

![20180523102904328][]

InitMapper：

<table style="table-layout:fixed;white-space:nowrap;width:0px;">    
 <tbody> 
  <tr style="height:115px;"> 
   <td style="color:rgb(57,57,57);border-color:rgb(167,167,167);white-space:pre-wrap;"> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">package com.test.sortpath;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import java.io.IOException;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.io.Text;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.Mapper;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">/**</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* 初始化数据的Mapreducer</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* @author root</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*/</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">public class InitMapper extends Mapper&lt;Text, Text, Text, Text&gt;{ </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;protected void map(Text key, Text value, Context context)</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;throws IOException, InterruptedException { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; String fn = context.getConfiguration().get("my.firstNode");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; String node = key.toString();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; if (node.equals(fn)) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;context.write(new Text(node + "\t" + 0+"\t"), value);//第一次初始化标记它到自已的距离为0。到其他节点的距离为无穷大</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; } else { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;context.write(new Text(node + "\t" + Integer.MAX_VALUE+"\t"), value);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">}</span> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

Mapper1:

<table style="table-layout:fixed;white-space:nowrap;width:0px;">    
 <tbody> 
  <tr style="height:75px;"> 
   <td style="color:rgb(57,57,57);border-color:rgb(167,167,167);white-space:pre-wrap;"> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">package com.test.sortpath;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import java.io.IOException;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.io.Text;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.Mapper;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import com.test.sortpath.RunJob.PathCounter;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">/**</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* 层层往外扩展的Mapreducer</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* @author root</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*/</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">public class Mapper1 extends Mapper&lt;Text, Text, Text, Text&gt;{ </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;private Text outKey = new Text();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;private Text outValue = new Text();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;protected void map(Text key, Text value, Context context)</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;throws IOException, InterruptedException { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; Node node = Node.fromMR(value.toString());//value :0 B:7 C:9 G:14</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; context.write(key, value);// 原始数据不做任何处理，输出 key:A value:0 B:7 C:9 在后面的reduce中会用到原始数据</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// G:14</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; if (node.isDistanceSet()) {//开始往外扩展</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;context.getCounter(PathCounter.MyCOUNT).increment(1);// i++</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// 获得任务的计数器。记录一共读到几个点。每读到一个点加1.</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;String backpointer = node.constructBackpointer(key.toString());//构造一个路径</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;for (int i = 0; i &lt; node.getAdjacentNodeNames().length; i++) {//开始扩展</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; String neighbor = node.getAdjacentNodeNames()[i];</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; // our neighbors are just a hop away</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; //</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; int neighborDistance = node.getDistance()</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; + Integer.parseInt(neighbor.split(":")[1]);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; // output the neighbor with the propagated distance and</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; // backpointer</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; //</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; outKey.set(neighbor.split(":")[0]);//以节点的名字为key</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; Node adjacentNode = new Node()</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; .setDistance(neighborDistance).setBackpointer(</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; backpointer);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; outValue.set(adjacentNode.toString());</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; System.out.println(" output -&gt; K[" + outKey + "],V["</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; + outValue + "]"); // key: B value:7 A</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; context.write(outKey, outValue);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">}</span> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

Reduce1:

Node:

<table style="table-layout:fixed;white-space:nowrap;width:0px;">    
 <tbody> 
  <tr style="height:96px;"> 
   <td style="color:rgb(57,57,57);border-color:rgb(167,167,167);white-space:pre-wrap;"> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">package com.test.sortpath;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import java.io.IOException;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import java.util.Arrays;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.commons.lang.StringUtils;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">/**</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* 解析value的对象。value：0 B:7 C:9 G:14</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;* @author root</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;*/</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">public class Node { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public static int INFINITE = Integer.MAX_VALUE;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; private int distance = INFINITE;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; //上一个节点</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; private String backpointer;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; //与该节点相邻的其他节点数组</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; private String[] adjacentNodeNames;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public static final char fieldSeparator = '\t';</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public int getDistance() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return distance;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public Node setDistance(int distance) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; this.distance = distance;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return this;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public String getBackpointer() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return backpointer;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public Node setBackpointer(String backpointer) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; this.backpointer = backpointer;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return this;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; /**</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;* A -&gt; B</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;* @param name</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;* @return</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;*/</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public String constructBackpointer(String name) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; StringBuilder backpointers = new StringBuilder();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; if (StringUtils.trimToNull(getBackpointer()) != null) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; backpointers.append(getBackpointer()).append("-&gt;");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; backpointers.append(name);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return backpointers.toString();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public String[] getAdjacentNodeNames() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return adjacentNodeNames;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public Node setAdjacentNodeNames(String[] adjacentNodeNames) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; this.adjacentNodeNames = adjacentNodeNames;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return this;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public boolean containsAdjacentNodes() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return adjacentNodeNames != null;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public boolean isDistanceSet() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return distance != INFINITE;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; @Override</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public String toString() { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; StringBuilder sb = new StringBuilder();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; sb.append(distance)</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; .append(fieldSeparator)</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; .append(backpointer);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; if (getAdjacentNodeNames() != null) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; sb.append(fieldSeparator)</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .append(StringUtils</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .join(getAdjacentNodeNames(), fieldSeparator));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return sb.toString();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; public static Node fromMR(String value) throws IOException { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; String[] parts = StringUtils.splitPreserveAllTokens(</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; value, fieldSeparator);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; if (parts.length &lt; 2) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; throw new IOException(</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "Expected 2 or more parts but received " + parts.length);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; Node node = new Node()</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; .setDistance(Integer.valueOf(parts[0]))</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; .setBackpointer(StringUtils.trimToNull(parts[1]));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; if (parts.length &gt; 2) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; node.setAdjacentNodeNames(Arrays.copyOfRange(parts, 2,</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parts.length));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; return node;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">}</span> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

RunJob:

<table style="table-layout:fixed;white-space:nowrap;width:0px;">    
 <tbody> 
  <tr style="height:83px;"> 
   <td style="color:rgb(57,57,57);border-color:rgb(167,167,167);white-space:pre-wrap;"> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">package com.test.sortpath;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.conf.Configuration;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.fs.FileSystem;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.fs.Path;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.io.Text;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.Job;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.lib.input.KeyValueTextInputFormat;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">public class RunJob { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;public static String firstNode = "A";</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;public static enum PathCounter { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; MyCOUNT// 计数器名字。定义一个计数器的名字</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;public static void main(String[] args) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; Configuration config = new Configuration();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; config.set("fs.defaultFS", "hdfs://node1:9000");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; config.set("my.firstNode", firstNode);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; // config.set("mapred.jar",</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; // "C:\\Users\\Administrator\\Desktop\\wc.jar");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; try { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;FileSystem fs = FileSystem.get(config);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;Job job = Job.getInstance(config);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setJobName("wc");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setJarByClass(RunJob.class);// job的入口类</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setMapperClass(InitMapper.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setMapOutputKeyClass(Text.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setMapOutputValueClass(Text.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setNumReduceTasks(0);// 没有reduce任务，也没有洗牌。</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;job.setInputFormatClass(KeyValueTextInputFormat.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;// 定义job任务输入数据目录和输出结果目录</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;// 把wc.txt上传到hdfs目录中/usr/intput/wc.txt</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;// 输出结果数据放到/usr/output/wc</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;FileInputFormat.addInputPath(job, new Path("/usr/input/data.txt"));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;// 输出结果数据目录不能存在，job执行时自动创建的。如果在执行时目录已经存在，则job执行失败。</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;Path output = new Path("/usr/output/init_shortpath");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;if (fs.exists(output)) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; fs.delete(output, true);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;FileOutputFormat.setOutputPath(job, output);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;boolean f = job.waitForCompletion(true);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;if (f) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; System.out.println("job执行成功！");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; int i = 0;// 迭代的次数</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; long nodecount = 0;// 节点统计数据</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; while (true) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;i++;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;// 开始迭代</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job = Job.getInstance(config);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setJobName("sp" + i);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setJarByClass(RunJob.class);// job的入口类</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setMapperClass(Mapper1.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; job.setReducerClass(Reduce1.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setMapOutputKeyClass(Text.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setMapOutputValueClass(Text.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;job.setInputFormatClass(KeyValueTextInputFormat.class);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;if(i==1){ </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; FileInputFormat.addInputPath(job, new Path(</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; "/usr/output/init_shortpath"));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;}else{ </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; FileInputFormat.addInputPath(job, new Path(</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; &nbsp; "/usr/output/shortpath"+(i-1)));</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;// 输出结果数据目录不能存在，job执行时自动创建的。如果在执行时目录已经存在，则job执行失败。</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;output = new Path("/usr/output/shortpath"+i);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;if (fs.exists(output)) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; fs.delete(output, true);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;FileOutputFormat.setOutputPath(job, output);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;f = job.waitForCompletion(true);</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;nodecount= job.getCounters().findCounter(PathCounter.MyCOUNT).getValue();//从计数器中拿到节点的总数</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;if (nodecount == 6) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; System.out.println("一共执行了"+i+"次Mapreducer");</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp; break;</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; } catch (Exception e) { </span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;// TODO Auto-generated catch block</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; &nbsp;e.printStackTrace();</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp; }</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">&nbsp;}</span> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <span style="font-family:'Microsoft YaHei', STXihei;color:rgb(0,0,0);background-color:transparent;">}</span> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: http://baike.baidu.com/view/349189.htm
[20180523102851223]: /images/20220524/9085ae2c9c0240e79437423e1ab3fa73.png
[20180523102858414]: /images/20220524/a7347087482b44629d2baa2daf3581aa.png
[20180523102904328]: /images/20220524/cec5793c505746b59ee50e8c57368b06.png