Java基于Dijkstra算法实现校园导游程序

Java基于Dijkstra算法实现校园导游程序

本文实例为大家分享了Dijkstra算法实现校园导游程序的具体代码，供大家参考，具体内容如下

应用设计性实验

1.问题描述

校网导游程序: 一个校园有若干景点，如正校门、人工湖、磁悬浮列车实验室、樱花大道、图书馆、体育场体育馆和礼堂等。实现一个为来访客 人提供信息在询服务的程序，如查询景点的详细信息,查询两个景点之间的一条最短路径。

2.实验要求

(1)设计你所在学校的校园平面图，所含景点不少于10个。(2)来访客人可以输人任一个景点的名称，查询景点的详细信息。(3)来访客人可以输人任何两个景点的名称，查询这两个景点之间的一条最短路径。

3.实现提示

以图中的顶点表示校园内各景点,存放景点代号、名称和简介等信息;以边表示路径，存放路径长度等相关信息，如实验图10.2所示。本题可采用邻接方阵或邻接表实现图的存储结构，利用迪杰斯特拉算法求得最短路径。

该程序“见错就收”、“见好就收”效率比较高——“剪枝”。

import java.util.ArrayList;

import java.util.Scanner;

public class TourGuide {

private static final Site[] sites = new Site[14];//以地点代号循序存放地点

private static final ArrayList 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 (siteInhttp://tro != null) {//其实这里也可以直接arrSites.indexOf(name)判断

System.out.println(siteIntro);

} else {

System.err.println("输入的地点名称不存在!");

}

break;

case 2:

System.out.print("输入所要查询最短路径的两地的名称(例如:正校门-礼堂): ");

String path = findShortestPath(scanner.next());

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

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。