学步园

 图的算法续

上一篇

5 最短距离
    在许多应用领域，带权图都被用来描述某个网络，比如通信网络、交通网络。这种情况下，各边的权重就对应于两点之间通信的成本或交通费用。此时，一类典型的问题就是：在任意指定的两点之间如果存在通路，那么最小的消费是多少。这类问题实际上就是带权图中两点之间最短路径的问题。
    对于求解最短路径问题：A)有时应当是有向图：如同一信道两个方向的信息流量不同，会造成信息从终端A到B和从终端B到A所需延时不同。B)有时应当是无向图：如从城市A到B和从城市B到A的公路长度都一样。

     定理：最短路径的子路径也是最短路径。

  5.1 求从某个源点到其余各点的最短路径
      迪克斯特拉Dijkstra算法执行规程：S 、V - S 是图的2个顶点集合；S是已求出的最短路径的终点集合；V - S 是尚未求出最短路径的终点集合。

     1) 初始化：

      S = {s}； distance(s) = 0； distancer(u_i) = w(s, u_i)或∞ ，(u_i ∈ V-S)；

   2) 选择distance(u_k) = min{distance(u_i)|u_i ∈ V-S }， u_k为下一条最短路径的终点；

   3) S = S ∪ { u_k }

   4) 以u_k 为”中转”，修正V-S中各个顶点distance；

      distancer(u_i) = min{ distance(u_i), distance(u_i) + w(u_k , u_i)}  (u_i ∈ V-S)

  5) 重复2) -4)步|V| -1 次

    Path对象：

public class Path {
  private int distance;  //起点与终点的距离
  private Vertex start;  //起点信息
  private Vertex end;    //终点信息
  private LinkedList pathInfo;//起点到终点的完整路径
 
  public Path() {
    this(Integer.MAX_VALUE,null,null);
  }
  public Path(int distance, Vertex start, Vertex end) {
    this.distance = distance;
    this.start = start;
    this.end = end;
    pathInfo = new LinkedListDLNode();
  }
 
  //判断起点与终点之间是否存在路径
  public boolean hasPath() {
    return distance!=Integer.MAX_VALUE&&start!=null&&end!=null;
  }
  //求路径长度
  public int pathLength(){
    if (!hasPath()) return -1;
    else if (start==end) return 0;
    else return pathInfo.getSize()+1;
  }

  //get&set methods
  public void setDistance(int dis){ distance = dis;}
  public void setStart(Vertex v){ start = v;}
  public void setEnd(Vertex v){ end = v;}
  public int getDistance(){ return distance;}
  public Vertex getStart(){ return start;}
  public Vertex getEnd(){ return end;}
  public Iterator getPathInfo(){
    return pathInfo.elements();
  }

  //清空路经信息
  public void clearPathInfo(){
    pathInfo = new LinkedListDLNode();
  }

  //添加路径信息
  public void addPathInfo(Object info){
    pathInfo.insertLast(info);
  }
}

关键算法 代码片段：

  //求顶点v到其他顶点的最短路径
  public Iterator shortestPath(Vertex v) {
    LinkedList sPath = new LinkedListDLNode();
    resetVexStatus();//重置图中各顶点的状态信息
    Iterator it = getVertex();//初始化，将v到各顶点的最短距离初始化为由v直接可达的距离
    for(it.first(); !it.isDone(); it.next()){
      Vertex u = (Vertex)it.currentItem();
      int weight = Integer.MAX_VALUE;
      Edge e = edgeFromTo(v,u);
      if (e!=null)
        weight = e.getWeight();
      if(u==v) weight = 0;
      Path p = new Path(weight,v,u);
      setPath(u, p);
    }
    v.setToVisited();//顶点v进入集合S,以visited=true表示属于S，否则不属于S
    sPath.insertLast(getPath(v));//求得的最短路径进入链接表
    for (int t=1;t<getVexNum();t++){//进行n-1次循环找到n-1条最短路径
      Vertex k = selectMin(it);//中间顶点k。可能选出无穷大距离的点，但不会为空
      k.setToVisited();        //顶点k加入S
      sPath.insertLast(getPath(k));  //求得的最短路径进入链接表
      int distK = getDistance(k);    //以k为中间顶点修改v到V-S中顶点的当前最短路径
      Iterator adjIt = adjVertexs(k);  //取出k的所有邻接点
      for(adjIt.first(); !adjIt.isDone(); adjIt.next()){
        Vertex adjV = (Vertex)adjIt.currentItem();
        Edge e = edgeFromTo(k,adjV);
        if ((long)distK+(long)e.getWeight()<(long)getDistance(adjV)){//发现更短的路径
          setDistance(adjV, distK+e.getWeight());
          amendPathInfo(k,adjV);  //以k的路径信息修改adjV的路径信息
        }
      }//for
    }//for(int t=1...
    return sPath.elements();
  }

  //在顶点集合中选择路径距离最小的
  protected Vertex selectMin(Iterator it){
    Vertex min = null;
    for(it.first(); !it.isDone(); it.next()){
      Vertex v = (Vertex)it.currentItem();
      if(!v.isVisited()){ min = v; break;}
    }
    for(; !it.isDone(); it.next()){
      Vertex v = (Vertex)it.currentItem();
      if(!v.isVisited()&&getDistance(v)<getDistance(min))
        min = v;
    }
    return min;
  }

  //修改到终点的路径信息
  protected void amendPathInfo(Vertex mid, Vertex end){
    Iterator it = getPath(mid).getPathInfo();
    getPath(end).clearPathInfo();
    for(it.first(); !it.isDone(); it.next()){
      getPath(end).addPathInfo(it.currentItem());
    }
    getPath(end).addPathInfo(mid.getInfo());
  }

  5.2 求每一对顶点之间的最短路径

      Floyd弗洛伊德算法, 基本思想是:

      1) 从 v_i 到 v_j 的所有可能存在的路径中，选出一条长度最短的路径。

      2) 若< v_i, v_j >存在，则存在路径{ v_i, v_j }// 路径中不含其它顶点

      3) 若< v_i,v₁>,< v₁, v_j >存在，则存在路径{ v_i, v₁, v_j }// 路径中所含顶点序号不大于1

      4) 若{ v_i,…,v₂}, { v₂,…, v_j }存在，则存在一条路径{ v_i, …, v₂, …v_j }// 路径中所含顶点序号不大于2

      …

      5) 依次类推，则 v_i 至 v_j 的最短路径应是上述这些路径中，路径长度最小者。