本文实例为大家分享了Dijkstra算法实现校园导游程序的具体代码，供大家参考，具体内容如下
应用设计性实验
1.问题描述
校网导游程序: 一个校园有若干景点，如正校门、人工湖、磁悬浮列车实验室、樱花大道、图书馆、体育场体育馆和礼堂等。实现一个为来访客 人提供信息在询服务的程序，如查询景点的详细信息,查询两个景点之间的一条最短路径。
2.实验要求
(1)设计你所在学校的校园平面图，所含景点不少于10个。
(2)来访客人可以输人任一个景点的名称，查询景点的详细信息。
(3)来访客人可以输人任何两个景点的名称，查询这两个景点之间的一条最短路径。
3.实现提示
以图中的顶点表示校园内各景点,存放景点代号、名称和简介等信息;以边表示路径，存放路径长度等相关信息，如实验图10.2所示。本题可采用邻接方阵或邻接表实现图的存储结构，利用迪杰斯特拉算法求得最短路径。
该程序“见错就收”、“见好就收”效率比较高——“剪枝”。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
import java.util.ArrayList;import java.util.Scanner; public class TourGuide { private static final Site[] sites = new Site[14];//以地点代号循序存放地点 private static final ArrayList<String> arrSites = new ArrayList<>(); private static final double[][] matrix = new double[14][14];//用来存放地点间的路径长度(对角线为0，不存在为INFINITY) static { sites[0] = new Site(0, "正校门", "正校门...");//初始化存放地点的数组 sites[1] = new Site(1, "东校门", "东校门..."); sites[2] = new Site(2, "西校门", "西校门..."); sites[3] = new Site(3, "北校门", "北校门..."); sites[4] = new Site(4, "食堂", "食堂..."); sites[5] = new Site(5, "磁悬浮列车实验室", "磁悬浮列车实验室..."); sites[6] = new Site(6, "樱花大道", "樱花大道..."); sites[7] = new Site(7, "图书馆", "图书馆..."); sites[8] = new Site(8, "体育场", "体育场..."); sites[9] = new Site(9, "体育馆", "体育馆..."); sites[10] = new Site(10, "游泳馆", "游泳馆..."); sites[11] = new Site(6, "礼堂", "礼堂..."); sites[12] = new Site(6, "教学楼", "教学楼..."); sites[13] = new Site(6, "宿舍", "宿舍..."); matrix[0][4] = 35;//初始化地点间的路径长度 matrix[0][11] = 5; matrix[1][10] = 75; matrix[1][13] = 10; matrix[2][4] = 30; matrix[2][7] = 5; matrix[3][6] = 15; matrix[3][7] = 50; matrix[3][9] = 15; matrix[3][10] = 20; matrix[4][8] = 60; matrix[4][11] = 40; matrix[5][8] = 45; matrix[5][11] = 10; matrix[8][11] = 50; matrix[9][10] = 20; matrix[9][13] = 100; matrix[11][12] = 25; matrix[12][13] = 20; for (Site site : sites) arrSites.add(site.getName()); //初始化ArrayList,用于以字符串的形式按顺序存放地点的名字 for (int i = 0; i < sites.length; i++) {//初始化地点间的路径长度 for (int j = 0; j < sites.length; j++) { if (i != j && matrix[i][j] == 0) matrix[i][j] = Double.POSITIVE_INFINITY; if (i > j) matrix[i][j] = matrix[j][i]; } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int select; while (true) { System.out.println("请输入您想了解的信息:\n1.查询地点详细信息\n2.查询地点间的最短路径\n3.退出系统"); select = scanner.nextInt(); switch (select) { case 1: System.out.print("输入查询地点的名称: "); String siteIntro = query(scanner.next()); if (siteIntro != null) {//其实这里也可以直接arrSites.indexOf(name)判断 System.out.println(siteIntro); } else { System.err.println("输入的地点名称不存在!"); } break; case 2: System.out.print("输入所要查询最短路径的两地的名称(例如:正校门-礼堂): "); String path = findShortestPath(scanner.next()); if (path != null) { System.out.println(path); } else { System.err.println("输入的所要查询最短路径的两地的名称或者格式有误!"); } break; case 3: System.exit(0); default: System.err.println("输入的选项有误!"); } System.out.println(); } } public static String query(String siteName) { int index = arrSites.indexOf(siteName); if (index == -1) { return null; } else { return sites[index].getIntro(); } } public static String findShortestPath(String path) { int indexOfSeparator = path.indexOf('-'); if (indexOfSeparator == -1) return null; String start = path.substring(0, indexOfSeparator); String end = path.substring(indexOfSeparator + 1); int indexOfStart = arrSites.indexOf(start); int indexOfEnd = arrSites.indexOf(end); if (indexOfStart == -1 || indexOfEnd == -1) return null; return dijkstra(indexOfStart, indexOfEnd); } private static String dijkstra(int start, int end) { int vertexCount = TourGuide.matrix.length; boolean[] isInUSet = new boolean[vertexCount];//数组元素默认初始化为false double[] distant = new double[vertexCount]; int[] parent = new int[vertexCount]; for (int i = 0; i < vertexCount; i++) { distant[i] = TourGuide.matrix[start][i]; parent[i] = start; } isInUSet[start] = true; distant[start] = 0; parent[start] = -1; for (int i = 0; i < vertexCount; i++) { double minCost = Double.POSITIVE_INFINITY; int minIndex = start; for (int j = 0; j < vertexCount; j++) { if (!isInUSet[j]) if (distant[j] < minCost) { minCost = distant[j]; minIndex = j; } } if (minCost < Double.POSITIVE_INFINITY) { isInUSet[minIndex] = true; } else { break; //处理的图为非连通图,即不输出相应路径(不存在能达到该顶点的路径) } if (minIndex == end)//找到后直接return提高效率 return printDijkstra(parent, distant, start, end); for (int j = 0; j < vertexCount; j++) {//迭代优化 if (!isInUSet[j] && distant[minIndex] + TourGuide.matrix[minIndex][j] < distant[j]) { distant[j] = distant[minIndex] + TourGuide.matrix[minIndex][j]; parent[j] = minIndex; } } } return null; } private static String printDijkstra(int[] parent, double[] distant, int start, int end) { int p = parent[end]; StringBuilder path = new StringBuilder(arrSites.get(end)); while (p != -1) { path.insert(0, arrSites.get(p) + "->"); p = parent[p]; } return arrSites.get(start) + "->" + arrSites.get(end) + " [" + path + "]: " + distant[end]; }} class Site { private int code; private String name; private String intro; public Site(int code, String name, String intro) { this.code = code; this.name = name; this.intro = intro; } public int getCode() { return code; } public void setCode(int code) { this.code = code; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getIntro() { return intro; } public void setIntro(String intro) { this.intro = intro; }} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_46539113/article/details/111128569
