解决方案 »

  1.   

    因为代码有错误。给你一个正确的实现,自己对照下:import java.util.ArrayList;   
    import java.util.List;   public class FloydInGraph {     
        private static int max=Integer.MAX_VALUE;  //dist[i][j]=max<==>i 和 j之间没有边   
        private int[][] dist;    //顶点i 到 j的最短路径长度,初值是i到j的边的权重     
        private int[][] path;     
        private List< Integer> result=new ArrayList< Integer>();     
        public static void main(String[] args) {   
            FloydInGraph graph=new FloydInGraph(6);   
            int[][] matrix={   
             {max,max,10,max,30,100}, 
                    {max,max,5,max,max,max},
                    {max,max,max,50,max,max},
                    {max,max,max,max,20,10},
                    {max,max,max,max,max,60},
                    {max,max,max,max,max,max}
            };   
            for(int i=0;i<6;i++)
             for(int j=0;j<6;j++)
             {
             graph.findCheapestPath(i,j,matrix);   
                    List< Integer> list=graph.result;   
                    System.out.print(i+" to "+j+",the cheapest path is: ");   
                    if(max==graph.dist[i][j])
                    {
                     System.out.println("There is no path from "+i+" to "+j);
                    }
                    else
                    {
                     System.out.println(list.toString());   
                     System.out.println("path distance: "+graph.dist[i][j]);
                    }   
             }
        }   
      
        public  void findCheapestPath(int begin,int end,int[][] matrix){   
            floyd(matrix);   
            result.clear();
            result.add(begin);   
            findPath(begin,end);   
            result.add(end);   
        }   
           
        public void findPath(int i,int j){   
            int k=path[i][j];   
            if(k==-1)return;   
            findPath(i,k);  
            result.add(k);   
            findPath(k,j);   
        }   
        public  void floyd(int[][] matrix){   
            int size=matrix.length;   
            for(int i=0;i< size;i++){   
                for(int j=0;j< size;j++){   
                    path[i][j]=-1;   
                    dist[i][j]=matrix[i][j];   
                }   
            }   
            for(int k=0;k< size;k++){   
                for(int i=0;i< size;i++){   
                    for(int j=0;j< size;j++){   
                        if(dist[i][k]!=max&&   
                            dist[k][j]!=max&&   
                            dist[i][k]+dist[k][j]< dist[i][j]){
                            dist[i][j]=dist[i][k]+dist[k][j];   
                            path[i][j]=k;   
                        }   
                    }   
                }   
            }   
               
        }   
           
        public FloydInGraph(int size){   
            this.path=new int[size][size];   
            this.dist=new int[size][size];   
        }   
    }