Java基于Dijkstra算法实现校园导游程序
作者:Feyl 发布时间:2021-10-15 15:38:18
标签:java,校园,导游
本文实例为大家分享了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<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
0
投稿
猜你喜欢
- 在Spring Boot集成Mybatis的项目中,如果出现SQL语句执行问题,我们需要进行排查。此时就需要打印对应的SQL语句,那么该如何
- 前言本文主要给大家介绍了关于利用Spring Data MongoDB持久化文档数据的相关内容,分享出来供大家参考学习,下面话不多说了,来一
- 本文实例讲述了Java数组传递及可变参数操作。分享给大家供大家参考,具体如下:方法可以操作传递和返回基本数据类型,但是方法中也可用来传递和返
- Object 类位于 java.lang 包中,是所有 Java 类的祖先,Java 中的每个类都由它扩展而来。定义Java类时如果没有显示
- 封装在如何理解面向对象这篇文章中,提到所谓的封装就是“功能都给你做好了,你不必去理解它是怎么写出来的,直接使用即可。”。但你得清楚一点,那就
- 本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法。分享给大家供大家参考,具体如下:在前面一篇《Java二叉搜索树遍历操作》中完成
- 1. Easy Rules 概述Easy Rules是一个Java规则引擎,灵感来自一篇名为《Should I use a Rules En
- 定义:当对象间存在一对多关系时,则使用观察者模式(Observer Pattern)。比如,当一个对象被修改时,则会自动通知它的依赖对象。特
- 本文实例讲述了java实现Xml与json之间的相互转换操作。分享给大家供大家参考,具体如下:旁白:最近关于xml与json之间的转换都搞蒙
- 本文以一个简单的实例来说明C#策略模式的实现方法,分享给大家供大家参考。具体实现方法如下:一般来说,当一个动作有多种实现方法,在实际使用时,
- 1.首先是编辑器的乱码,这个很好解决,file->settings->appearence里面有个Name设置成支持中文的字 体
- 一. 依赖管理Ⅰ. 部分dependency导入时为啥不需要指定版本?我们创建项目时添加的依赖并没有帮我们指定版本号<>,那Sp
- Java身份证验证方法实例详解身份证号码验证 1、号码的结构 公民身份号码是特征组合码,由十七位数字本体码和一位校验码组成。排列顺序从左至右
- Ribbon是Spring Cloud Netflix全家桶中负责负载均衡的组件,它是一组类库的集合。通过Ribbon,程序员能在不涉及到具
- 1.取整运算符取整从字面意思理解就是被除数到底包含几个除数,也就是能被整除多少次,那么它有哪些需要注意的地方呢?先看下面的两端代码: &nb
- 最大数给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个
- 一、什么是外观模式定义:为子系统中的一组接口提供一个一致的界面,用来访问子系统中的一群接口。外观模式组成:Facade:负责子系统的的封装调
- FTP简介文件传输协议(File Transfer Protocol,FTP)是用于在网络上进行文件传输的一套标准协议,它工作在 OSI 模
- 实例如下:import java.util.concurrent.CountDownLatch;import java.util.concu
- 在前面的《基于任务的异步编程模式(TAP)》文章中讲述了.net 4.5框架下的异步操作自我实现方式,实际上,在.net 4.5中部分类已实