算法设计报告代码

 1 package shortesP;
 2 
 3 import java.util.Scanner;
 4 
 5 public class DijkstraTest {
 6      
 7     public static void main(String[] args) {
 8         // TODO Auto-generated method stub
 9         int[][] weight= {{0,30,-1,-1,-1,-1,-1,70,-1,-1,-1,-1},{30,0,30,-1,40,-1,-1,-1,-1,-1,-1,-1},
10                          {-1,30,0,35,-1,40,-1,-1,-1,-1,-1,-1,},{-1,-1,35,0,-1,-1,50,-1,-1,-1,-1,-1},
11                          {-1,40,-1,-1,0,35,-1,25,-1,-1,-1,-1},{-1,-1,40,-1,35,0,60,-1,-1,-1,-1,-1},
12                          {-1,-1,-1,50,-1,60,0,-1,-1,-1,85,-1},{70,-1,-1,-1,25,-1,-1,0,15,30,-1,-1},
13                          {-1,-1,-1,-1,-1,-1,-1,15,0,10,-1,-1},{-1,-1,-1,-1,-1,-1,-1,30,10,0,65,60},
14                          {-1,-1,-1,-1,-1,-1,85,-1,-1,65,0,50},{-1,-1,-1,-1,-1,-1,-1,-1,-1,60,50,0}};
15         String[] str= {"学生舍14号楼","成都大学13舍","成都大学12舍","成都大学11舍","第9教学楼",
16                        "医学院","通威楼","医护学院","东北门","第10教学楼","新图书馆","综合教学楼B"};
17         int len=str.length;
18         Dijkstra dijkstra=new Dijkstra(len);
19         //依次让各点当源点，并调用dijkstra函数
20         Scanner s=new Scanner(System.in);
21         System.out.println("请输入起点位置：");
22         String V=s.nextLine();
23         
24         Scanner S=new Scanner(System.in);
25         System.out.println("请输入终点位置：");
26         String H=S.nextLine();
27     
28         int v=getIndex(V,str);
29         int h=getIndex(H,str);
30         
31         dijkstra.dijkstra(weight, str,v,h);
32     }
33     public static int getIndex(String s,String[] str) {
34         int k=-1;
35         for(int i=0;i<str.length;i++) {
36             if(str[i].equals(s)) {
37                 k=i;
38             }
39         }
40         return k;
41     }
42  
43 }

 1 package shortesP;
 2 import java.util.*;
 3 
 4 public class Dijkstra {
 5     private Queue<Integer> visited;
 6     int[] distance;
 7     
 8     public Dijkstra(int len) {
 9         // TODO Auto-generated constructor stub
10         visited=new LinkedList<Integer>();
11         distance=new int[len];
12         
13     }
14     
15     private int getIndex(Queue<Integer> q,int[] dis)
16     {
17         int k=-1;
18         int min_num=Integer.MAX_VALUE;
19         for(int i=0;i<dis.length;i++)
20         {
21             if(!q.contains(i))
22             {
23                 if(dis[i]<min_num)
24                 {
25                     min_num=dis[i];
26                     k=i;
27                 }
28             }
29         }
30         return k;
31     }
32     public void dijkstra(int[][] weight,Object[] str,int v,int h)
33     {
34         HashMap<Integer, String> path;       //创建哈希图path用于存储路径，key值存储当前点位置下标      
35         path=new HashMap<Integer, String>(); //value存储起点到当前点的路径        
36         for(int i=0;i<str.length;i++)
37             path.put(i, "");
38         
39         //初始化路径长度数组distance
40         for(int i=0;i<str.length;i++)
41         {
42             path.put(i, path.get(i)+""+str[v]);    //初始化路径为起点
43             if(i==v)                               
44                 distance[i]=0;                     //起点distance设为0
45             else if(weight[v][i]!=-1)             
46             {
47                 distance[i]=weight[v][i];          //遍历其他点，若与起点间直接可达，则设置其distance为它们之间的权重
48                 path.put(i, path.get(i)+"-->"+str[i]);//初始化起点可直接到达的路径：key:可直达点 value:起点-->可直达点
49             }
50             
51             else
52                 distance[i]=Integer.MAX_VALUE;     //若不可达，则设为integer的最大值表示无穷大
53         }
54         visited.add(v);                            //将起点加入visited队列（表示已遍历的点）
55         while(!(visited.contains(h))||visited.size()<str.length) //若visited中已包含终点则说明，此时终点的path一定最短
56         {
57             int k=getIndex(visited,distance);//获取未访问点中距离源点最近的点
58             visited.add(k);                  //将最近点加入已访问点的集合中，并以该点作为中间点
59             if(k!=-1)
60             {
61                 for(int j=0;j<str.length;j++)
62                 {
63                     if(weight[k][j]!=-1)//判断k点能够直接到达的点
64                     {
65                         //通过遍历各点，比较是否有比当前更短的路径，有的话，则更新distance，并更新path。
66                         if(distance[j]>distance[k]+weight[k][j])
67                         {
68                             distance[j]=distance[k]+weight[k][j];
69                             path.put(j, path.get(k)+"-->"+str[j]);                    
70                         }
71                     }
72                     
73                 }
74             }
75         }
76             
77         System.out.printf(str[v]+"-->"+str[h]+":"+distance[h]+" ");    
78         if(distance[h]==Integer.MAX_VALUE) {
79             System.out.print(str[v]+"-->"+str[h]+"之间没有可通行路径");
80         }
81         else {
82             System.out.print(str[v]+"-"+str[h]+"之间有最短路径，具体路径为："+path.get(h).toString());
83             System.out.println();
84         }
85         visited.clear();
86         
87     }
88     
89 }