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, "正校門", "正校門...");//初始化存放地點的數(shù)組
? ? ? ? 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.退出系統(tǒng)");
? ? ? ? ? ? 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];//數(shù)組元素默認初始化為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++) {//迭代優(yōu)化
? ? ? ? ? ? ? ? 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;
? ? }
}