Java基於Dijkstra演演算法實現校園導遊程式

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;
    }
}