import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
*
* @author 孤云挂月
* 寻路算法很多,没有什么高深的技术,仅仅是提供一个能用的自编算法
* 可以用来查找相关连的所有路径及最短路径的,可以正查也可以逆查
* 耗时相对也比较短
*
* */
public class ShowMeTheWay {
/**
* @param args
*/
private List<Line> link=new ArrayList<Line>();
private Line target=null;
private String result=null;
public boolean addLine(Line line){
//应添加节点连接是否已添加过
link.add(line);
//System.out.println("line:" + line.getPoint_1() + line.getPoint_2());
System.out.println("line:" + line.toString());
return true;
}
public void setTarget(Line line){
System.out.println("target:" + line.toString());
target=line;
}
public void display(){
System.out.println("最短路径:" + result);
}
public void calculation(){
System.out.println("calculation start:" + System.currentTimeMillis());
Map<String,LineSet> map=new HashMap<String,LineSet>();
for(int i=0;i<link.size();i++){
Line tmp=link.get(i);
//端点1 增加映射
LineSet ls_1 =map.get(tmp.getPoint_1());
if(ls_1==null){
LineSet ls=new LineSet();
ls.setVertex(tmp.getPoint_1());
ls.addLine(tmp.getPoint_2());
map.put(tmp.getPoint_1(), ls);
}else{
//if(ls_1.checkLine(tmp.getPoint_2())==false){
ls_1.addLine(tmp.getPoint_2());
//}
}
//端点2 增加映射
LineSet ls_2 =map.get(tmp.getPoint_2());
if(ls_2==null){
LineSet ls=new LineSet();
ls.setVertex(tmp.getPoint_2());
ls.addLine(tmp.getPoint_1());
map.put(tmp.getPoint_2(), ls);
}else{
//if(ls_2.checkLine(tmp.getPoint_1())==false){
ls_2.addLine(tmp.getPoint_1());
//}
}
}
List<LineSet> rList=new ArrayList<LineSet>();
boolean flag=false;
LinkedList<LineSet> ll=new LinkedList<LineSet>();
LineSet ls=map.get(target.getPoint_1());
if(ls==null){
System.out.println("无此端点");
return ;
}
for(int o=0;o<ls.getList().size();o++){
if(ls.getList().toArray()[o].equals(target.getPoint_2())){
result=target.getPoint_1() + "->" +target.getPoint_2();
flag=true;
break;
}else{
LineSet tls=new LineSet();
tls.setVertex((String) ls.getList().toArray()[o]);
tls.makeResult(target.getPoint_1());
tls.addLine(target.getPoint_1());
//tls.addLine((String) ls.getList().toArray()[o]);
ll.add(tls);
}
}
while(flag==false){
LinkedList<LineSet> tll=new LinkedList<LineSet>();
while(ll.size()!=0){
LineSet vv=ll.pop();
LineSet _tls =map.get(vv.getVertex());
for(int m=0;m<_tls.getList().size();m++){
LineSet v=new LineSet();
v.setVertex(vv.getVertex());
v.setLines(vv.getLines());
v.setResult(vv.getResult());
if(v.checkLine((String)_tls.getList().toArray()[m])){
v.addLine(v.getVertex());
v.makeResult(v.getVertex());
//v.makeResult((String)_tls.getList().toArray()[m]);
v.setVertex((String)_tls.getList().toArray()[m]);
tll.add(v);
if(((String)_tls.getList().toArray()[m]).equals(target.getPoint_2())){
v.makeResult((String)_tls.getList().toArray()[m]);
rList.add(v);
//System.out.println(v.getResult());
//System.out.println(v.getResult());
//System.out.println("===================================");
}//else{
//System.out.println(v.getResult());
//}
//System.out.println(v.getResult());
}
}
}
//System.out.println("1");
if(tll.size()==0){
flag=true;
break;
}else{
ll=tll;
}
}
System.out.println("结果个数:"+rList.size());
int sResult=-1;
for(int n=0;n<rList.size();n++){
if(sResult==-1){
sResult=0;
result=rList.get(0).getResult();
}else{
if(rList.get(n).getResult().length()<result.length()){
sResult=n;
result=rList.get(0).getResult();
}
}
System.out.println("第"+(n+1)+"种路径:"+rList.get(n).getResult());
}
//if(sResult!=-1){
// System.out.println("最短路径:"+result);
//}
System.out.println("calculation finish:" + System.currentTimeMillis());
}
public static void main(String[] args) {
ShowMeTheWay smt=new ShowMeTheWay();
/*
smt.addLine(new Line("1","2"));
smt.addLine(new Line("1","3"));
smt.addLine(new Line("2","3"));
smt.addLine(new Line("3","4"));
smt.addLine(new Line("5","4"));
smt.setTarget(new Line("3","5"));
*/
//只需要输入所有点之间的链接(无顺序要求,不限于数字输入)
smt.addLine(new Line("0", "1"));
smt.addLine(new Line("0", "2"));
smt.addLine(new Line("1", "3"));
smt.addLine(new Line("1", "4"));
smt.addLine(new Line("1", "9"));
smt.addLine(new Line("3", "4"));
smt.addLine(new Line("3", "5"));
smt.addLine(new Line("2", "5"));
smt.addLine(new Line("5", "6"));
smt.addLine(new Line("6", "7"));
smt.addLine(new Line("7", "8"));
smt.addLine(new Line("4", "9"));
//输入起始点
smt.setTarget(new Line("2","9"));
smt.calculation();
//显示结果
smt.display();
}
}
java快速易懂寻路算法


在IT领域,寻路算法是计算机科学中的一个重要概念,尤其在游戏开发、网络路由、物流配送等场景中广泛应用。Java作为一种流行的编程语言,也经常被用于实现各种寻路算法。本篇文章将深入探讨标题和描述中提及的"java快速易懂寻路算法",以及如何在Java中实现这样的算法。 我们要理解什么是寻路算法。寻路算法是解决图论问题的一种方法,其目标是在图中找到两个节点之间的路径。这些路径可能是最短的、最长的,或者是满足特定条件的。在Java中,我们通常会用到的数据结构有数组、链表、队列和栈,以及图的表示方式,如邻接矩阵或邻接表。 描述中提到的“没有什么高深的技术”,意味着这个算法可能相对简单,易于理解和实现。它不仅能够查找所有相关的路径,还能进行正查和逆查。正查是从起点到终点的搜索,而逆查则是从终点到起点的搜索。这两种方式对于不同的应用场景都有其价值,例如在导航系统中,用户可能需要知道从当前位置到目的地的所有可能路线,或者在游戏设计中,AI角色可能需要找到多个到达目标的路径以避免障碍。 寻路算法有很多经典的选择,例如Dijkstra算法、A*算法、Floyd-Warshall算法和Bellman-Ford算法。其中,Dijkstra算法适合寻找图中最短路径,它使用优先队列来保证每次扩展的是当前最短路径的节点。A*算法是在Dijkstra的基础上加入了启发式函数,使得搜索更高效,尤其是在大型图中。Floyd-Warshall和Bellman-Ford算法则用于计算所有节点对之间的最短路径,前者适用于所有边权重非负的情况,后者能处理负权边但效率较低。 在Java中实现这些算法,你需要了解基本的图数据结构的构建,例如使用二维数组或ArrayList来表示邻接矩阵,或者使用LinkedList来表示邻接表。同时,还需要熟悉优先队列(PriorityQueue)以及如何使用它来优化搜索过程。对于启发式函数,你可以考虑使用曼哈顿距离、欧几里得距离或者其他与实际场景相关的函数。 "FindWay"这个文件名很可能是指实现了寻路算法的类或者包。在代码实现中,这个类可能会包含一些核心方法,比如`findPath(startNode, endNode)`用于寻找起点到终点的路径,以及`reversePath(path)`用于反转路径。同时,为了实现正查和逆查,可能还会包含`getAllPaths(startNode)`和`getAllPaths(endNode)`方法。 总结来说,"java快速易懂寻路算法"是指在Java中设计和实现的一种简单易懂的寻路算法,它可以快速地找出图中节点之间的路径,包括最短路径,并支持正查和逆查。这种算法的实现涉及到图的表示、路径搜索策略以及可能的启发式优化。通过学习和理解这些基础知识,开发者可以为各种应用场合创建高效且实用的寻路解决方案。




























- 1

- #完美解决问题
- #运行顺畅
- #内容详尽
- #全网独家
- #注释完整

- 粉丝: 6
- 资源: 5
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


最新资源
- springbootAI医疗诊断系统类情感分析平台源码+论文+视频2_最新.zip
- 鸿蒙网络编程示例仓库,包括鸿蒙网络编程相关的主要网络协议及UI组件 本仓库所有示例均为完整代码,使用ArkTS语言或仓颉语言编写,包括详细的代码注释及完整的运行演示文档,都可以独立编译运行
- java虚拟机、java jvm 、面试八股文、面试,自学
- springbootAI医疗诊断系统类客户管理系统源码+论文+视频2_最新.zip
- springbootAI医疗诊断系统类企业管理平台源码+论文+视频2_最新.zip
- springboot企业协作平台类用户反馈平台源码+论文+视频2_最新.zip
- **5KW高效率MPPT太阳能控制器:基于STM32F103RCT6主控平台的全面保护与在线升级方案**,基于STM32F103RCT6的5KW高效MPPT太阳能控制器:支持485通讯与高压电池组供电
- 吴恩达新作《如何在人工智能领域建立你的职业生涯》
- springboot企业健康管理平台类电商产品推荐平台源码+论文+视频2_最新.zip
- springboot企业内部数据分析平台类环境监控平台源码+论文+视频2_最新.zip
- springboot企业健康管理平台类跨平台销售系统源码+论文+视频2_最新.zip
- springboot企业健康管理平台类交通信息平台源码+论文+视频2_最新.zip
- springboot仓储管理类金融智能平台源码+论文+视频2_最新.zip
- springboot企业云存储平台类客户管理系统源码+论文+视频2_最新.zip
- 基于蒙特卡洛方法的风电与光伏功率场景生成技术:考虑时间相关性的MATLAB实现,基于蒙特卡洛方法的风电光伏功率场景生成方法(含时间相关性考虑及概率计算),基于蒙特卡洛的风电功率 光伏功率场景生成方法
- 鸿蒙原生ArkTS与JavaScript通信框架


