fac4_5.java

java 算法设计与分析的好资料.由王晓东先生主编.

//
//本程序取自王晓东编著“算法分析与设计”第 121 页，例
//单源最短路径问题贪心(dijksra)解法
   public class Fac4_5{
   public static void dijkstra(int v,float [][]a, float [] dist, int [] prev)
   {
      int n=dist.length-1;
      if(v<1||v>n)return;
      boolean []s=new boolean[n+1];
     
      for (int i = 1; i < n; i++){ 
         dist[i]=a[v][i]; s[i]=false;
         if(Math.abs(dist[i]-Float.MAX_VALUE)<1E-10)prev[i]=0;
         else  prev[i]=v;
       }
            
      dist[v]=0;s[v]=true;
      for(int i=1;i<=n;i++){
         float temp=Float.MAX_VALUE;
         int u=v;
        for (int j = 1; j <= n; j++) 
         if(!s[j] && (dist[j]<temp)){
          u=j;
          temp=dist[j];
          }
        s[u]=true;
       for(int j=1;j<=n;j++)
        if(!s[j]&&(a[u][j]<Float.MAX_VALUE)){
         float newdist=dist[u]+a[u][j];
         if(newdist<dist[j]){
          //dist[j]减少
         dist[j]=newdist;
         prev[j]=u;
         }
        }
     }
   }
    public static void main(String argc[])
      {
       int v1=1;
       final float ff=Float.MAX_VALUE;
       float [][]a1={{0.0f,0.0f,0.0f,0.0f,0.0f,0.0f},
                     {0.0f,0.0f, 10f,  ff, 30f,100f},
                     {0.0f,0.0f,0.0f, 50f,  ff,  ff},
                     {0.0f,  ff,  ff,0.0f,  ff, 10f},
                     {0.0f,  ff,  ff, 20f,0.0f, 60f},
                     {0.0f,  ff,  ff,  ff,  ff,0.0f}};
       int n1=a1[1].length;
       float []d1=new float[n1];
       int []p1=new int[n1];
       dijkstra(v1,a1,d1,p1);
       System.out.println("输出顶点前置点顺序结果  ");
      for(int i=1;i<n1;i++)
      System.out.println("prev["+i+"]="+p1[i]+" dist["+i+"]="+d1[i]);
      }
   }