Dijkstra算法求一点到所有点的最短路径.doc

Dijkstra算法求一点到所有点的最短路径
  (2010-03-25 23:22:01)
转载▼
标签： 
迪杰斯特拉

求一点

到所有点的

最短路径

dijkstra

it
分类： 数据结构&算法设计与分析
//迪杰斯特拉求一点到所有点的最短路径

-------------------------------------------------------------------------
迪杰斯特拉求一点到所有点的最短路径（Dijkstra）算法描述
1、选定起点放入E集合中。
2、把未选点放入R集合中，写出E集合中所有点到R集合中所有点的路径放入Path集合（以“E中的点—R中的点=权值”为形式）。
3、在Path中选择权值最小的路径，在Path中标*号（不参与下一次在Path中选择权值最小的路径），再放入S中。然后把这个路径中的从R中选出的点（路径中的终点）加入E，从R中移除。
4、返回2到3进行循环，直到R为空，就到5
5、S集合中就是起点到其他点的最短路径。
---------------------------------------------------------------------------
表格演示：

E（已选点）
R（未选点）
Path（路径）
S（选中路径）
0
1，2，3，4
*0-1=1
0-2=3
0-3=∞
0-4=∞
0-1=1
0，1
2，3，4
0-1-2=∞
0-1-3=1+4=5
0-1-4=∞
*0-2=3
0-3=∞
0-4=∞
0-2=3
0，1，2
3，4
0-2-3=3+2=5
0-2-4=3+2=5
0-1-2=∞
*0-1-3=1+4=5
0-1-4=∞
0-3=∞
0-4=∞
0-1-3=1+4=5
0，1，2，3
4
0-1-3-4=1+4+1=6
*0-2-4=3+2=5
0-2-3=3+2=5
0-1-2=∞
0-1-4=∞
0-3=∞
0-4=∞
0-2-4=3+2=5

 ------------------------------------------------------------------------------------------
//////////////////////////////////////
代码实现程序结构：

---------------------------------------------------------------------------------------------
最终生成的树结构转化为以下的表结构：
（在代码中对应的是Tree数组）

id
0
1
2
3
3
4
4

root
0
0
0
1
2
2
3

right
99
1
3
5
5
5
6

flag
0
1
1
1
1
1

id：到达的点。
root：是id中对应的根。
right：是id所对应的权值加上其root的权值。注，其表生成时是从左往右的，故权值是可以累加的。
flag：在算法描述中的*号标记。
----------------------------------------------------------------------------------------------
res数组实现 算法描述中的E R集合
（最终生成的在代码中对应的res数组表）
res
id   0 1 2 3 4
flag 2 1 1 1 1
注：起点flag标记为2
-----------------------------------------------------------------------------------------------
//结果使用递归打印
//4<-2<-0
//3<-2<-0
//3<-1<-0
//2<-0
//1<-0
----------------------------------------------------------------------------------------------
//Java代码//
class Tree{
 int id=0;
 int root=0;
 int right=0;
 int flag=0;
 public void setAll(int id,int ro,int ri,int fl){
  this.flag=fl;
        this.id=id;
        this.right=ri;
        this.root=ro;
 }
 public void setFlag(int flag) {
  this.flag = flag;
 }
 public void setId(int id) {
  this.id = id;
 }
 public void setRight(int right) {
  this.right = right;
 }
 public void setRoot(int root) {
  this.root = root;
 }
 public void get_r(Tree t){
     this.flag=t.flag;
     this.id=t.id;
     this.right=t.right;
     this.root=t.root;
 }
 public boolean equals(Tree t){
  if((this.flag==t.flag)&&(this.id==t.id)&&(this.right==t.right)&&(this.root==t.root)){
   return true;
  }else{
   return false;
  }
 }
 public boolean isZero(){
  if((this.flag==0)&&(this.id==0)&&(this.right==0)&&(this.root==0)){
   return true;
  }else{
   return false;
  }
 }
}
class RESet{
 int id=0;
 int flag=0;
 public void setId(int id){
  this.id=id;
 }
 public void setFlag(int flag){
  this.flag=flag;
 }
}
public class DijkstraFindRoad {
 static int node[][]={
    //0, 1, 2, 3, 4
 {99, 1, 3,99,99},
 { 1,99,99, 4,99},
 { 3,99,99, 2, 2},
 {99, 4, 2,99, 1},
 {99,99, 2, 1,99}
 };
 public DijkstraFindRoad(){

 }
    public static int printRoad(Tree []t,int i){//打印路径
     System.out.print("<-"+t[ getRtNum_r(t,t[i])].id);
     if(t[i].right==99){
      return 0;
     }else{
      printRoad(t, getRtNum_r(t,t[ getRtNum_r(t,t[i])]));
     }

     return 1;
    }
 public static void removeSameValue(Tree []tq){/////去除重复
        int flag=0,j=0;
        for(int i=0;i<tq.length;i++){
         for(j=0;j<tq.length;j++){
          if(tq[i].equals(tq[j])&&(!tq[i].isZero())){
          flag=i;
          }
         }
        }
        tq[flag].setAll(0,0,0,0);
 }
 public static int getRtNum_r(Tree[] tq,Tree t){//取得t的根的物理地址
  int rti=0;
    for(int i=0;i<tq.length;i++){
     if(t.root==tq[i].id){
      rti=i;break;
     }
    }
    return rti;
 }
 public static boolean isRoadFull(Tree[] t,RESet []rs){//是否所有路径都已选择
  int counter=0;
        for(int i=1;i<t.length;i++){
         if(t[i].flag==1)counter++;
        }
        if(rs.length==counter){
         return true;
        }
        return false;
 }
    public static void main(String args[]){
       Tree t[]=new Tree[20];
       Tree temp=new Tree();//做交换用
       RESet res[]=new RESet[5];
       int start=0;//指定起点，从0点开始
       //////////////////////////////////////初始化
       for(int i=0;i<res.length;i++){
        res[i]=new RESet();
        res[i].setId(i);
       }
       for(int i=0;i<t.length;i++){
        t[i]=new Tree();
       }
       res[start].setFlag(2);
       t[0].setId(start);
       t[0].setRoot(0);
       t[0].setRight(99);
       t[0].setFlag(0);
       //////////////////////////////////////

       int ti=1;
       int j=0;
       int xi=0,yj=0,counter=0;

       ti=1;
       while(true){
    //////////////////////////////////////////////////
       yj=0;
       for(int i=0;i<res.length;i++){
        if(res[i].flag==0) yj++;
       }
       xi=res.length-yj;
       //System.out.println("xi:"+xi+" "+"yj:"+yj+"||ti:"+ti);
       //////////////////////////////////////选取点操作
       int ii=xi-1,nbeg=ti,nend=0;     
         for(j=xi-1;j<res.length;j++){//1
          if(node[ii][j]!=99){//if         
           t[ti].setId(j);
           t[ti].setRoot(ii);
           t[ti].setRight(node[ii][j]);
           ti++;
          }//if             
         }//1
       nend=ti;
      //////////////////////////////////////////加权操作
            //System.out.println("ROOT:"+ getRtNum_r(t,t[4]));
               for(int i=nbeg;i<nend;i++){
                if(t[i].root!=0){
                t[i].setRight(t[ getRtNum_r(t,t[i])].right+t[i].right);

                }
               }
      /////////////////////////////////////////选最小权值
       int min=99;
       int f=0;
       for(int i=0;i<t.length;i++){
        if((t[i].right!=0)&&(t[i].flag!=1)&&(t[i].right<min)){
         min=t[i].right;
         f=i;
        }
       }
         ///////////////////////////////////////选最小权值，做标记
       t[f].setFlag(1);
       res[t[f].id].flag=1;

       ///////////////////////////////////////
       //System.out.println("11111:"+t[f].id+":"+t[f].root+":"+t[f].right+":"+t[f].flag);
       //////////////////////////////////////////////////////////////////////////////////   
       if(isRoadFull(t,res))break;
       }
      /////////////////////////////////////////////
       removeSameValue(t);
       ////////////////////////////////////////////
       ////////////////////////////////////////////
//       for(int si=0;si<res.length;si++){
//           System.out.println(res[si].id+":"+res[si].flag);
//       }
//       for(int si=0;si<t.length;si++){
//        System.out.println(t[si].id+":"+t[si].root+":"+t[si].right+":"+t[si].flag);
//       }
       //////////////////////////////////////打印路径
       int n=res.length;
      for(int i=n;i>0;i--){
      System.out.print(t[i].id);
         printRoad(t,i);
      System.out.println();
      }

    }
}