Java基于Dijkstra算法實(shí)現(xiàn)校園導(dǎo)游程序

更新時(shí)間：2022年03月17日 11:20:54 作者：Feyl

這篇文章主要為大家詳細(xì)介紹了Java基于Dijkstra算法實(shí)現(xiàn)校園導(dǎo)游程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了Dijkstra算法實(shí)現(xiàn)校園導(dǎo)游程序的具體代碼，供大家參考，具體內(nèi)容如下

應(yīng)用設(shè)計(jì)性實(shí)驗(yàn)

1.問題描述

校網(wǎng)導(dǎo)游程序: 一個(gè)校園有若干景點(diǎn)，如正校門、人工湖、磁懸浮列車實(shí)驗(yàn)室、櫻花大道、圖書館、體育場體育館和禮堂等。實(shí)現(xiàn)一個(gè)為來訪客人提供信息在詢服務(wù)的程序，如查詢景點(diǎn)的詳細(xì)信息,查詢兩個(gè)景點(diǎn)之間的一條最短路徑。

2.實(shí)驗(yàn)要求

(1)設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。
(2)來訪客人可以輸人任一個(gè)景點(diǎn)的名稱，查詢景點(diǎn)的詳細(xì)信息。
(3)來訪客人可以輸人任何兩個(gè)景點(diǎn)的名稱，查詢這兩個(gè)景點(diǎn)之間的一條最短路徑。

3.實(shí)現(xiàn)提示

以圖中的頂點(diǎn)表示校園內(nèi)各景點(diǎn),存放景點(diǎn)代號(hào)、名稱和簡介等信息;以邊表示路徑，存放路徑長度等相關(guān)信息，如實(shí)驗(yàn)圖10.2所示。本題可采用鄰接方陣或鄰接表實(shí)現(xiàn)圖的存儲(chǔ)結(jié)構(gòu)，利用迪杰斯特拉算法求得最短路徑。

該程序“見錯(cuò)就收”、“見好就收”效率比較高——“剪枝”。

import java.util.ArrayList;
import java.util.Scanner;
?
public class TourGuide {
? ? private static final Site[] sites = new Site[14];//以地點(diǎn)代號(hào)循序存放地點(diǎn)
? ? private static final ArrayList<String> arrSites = new ArrayList<>();
? ? private static final double[][] matrix = new double[14][14];//用來存放地點(diǎn)間的路徑長度(對角線為0，不存在為INFINITY)
?
? ? static {
? ? ? ? sites[0] = new Site(0, "正校門", "正校門...");//初始化存放地點(diǎn)的數(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, "磁懸浮列車實(shí)驗(yàn)室", "磁懸浮列車實(shí)驗(yàn)室...");
? ? ? ? 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, "教學(xué)樓", "教學(xué)樓...");
? ? ? ? sites[13] = new Site(6, "宿舍", "宿舍...");
? ? ? ? matrix[0][4] = 35;//初始化地點(diǎn)間的路徑長度
? ? ? ? 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,用于以字符串的形式按順序存放地點(diǎn)的名字
?
? ? ? ? for (int i = 0; i < sites.length; i++) {//初始化地點(diǎn)間的路徑長度
? ? ? ? ? ? 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.查詢地點(diǎn)詳細(xì)信息\n2.查詢地點(diǎn)間的最短路徑\n3.退出系統(tǒng)");
? ? ? ? ? ? select = scanner.nextInt();
? ? ? ? ? ? switch (select) {
? ? ? ? ? ? ? ? case 1:
? ? ? ? ? ? ? ? ? ? System.out.print("輸入查詢地點(diǎn)的名稱: ");
? ? ? ? ? ? ? ? ? ? String siteIntro = query(scanner.next());
? ? ? ? ? ? ? ? ? ? if (siteIntro != null) {//其實(shí)這里也可以直接arrSites.indexOf(name)判斷
? ? ? ? ? ? ? ? ? ? ? ? System.out.println(siteIntro);
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? System.err.println("輸入的地點(diǎn)名稱不存在!");
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? 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("輸入的選項(xiàng)有誤!");
? ? ? ? ? ? }
? ? ? ? ? ? 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ù)組元素默認(rèn)初始化為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; ? ? ?//處理的圖為非連通圖,即不輸出相應(yīng)路徑(不存在能達(dá)到該頂點(diǎn)的路徑)
? ? ? ? ? ? }
? ? ? ? ? ? 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;
? ? }
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: