java迷宫最短路径_求java算法源代码求出汽车从起点S出发到达终点T的一条行驶路程最短的路线

❶ java迷宫算法问题（用栈实现）有算法简述

importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Scanner;

publicclassTest{

	publicstaticvoidmain(String[]args)throwsFileNotFoundException{
		Scannerinput=newScanner(newFile("Maze2tong.txt"));
		introw=0;
		char[][]Mazemap=newchar[12][58];
		while(input.hasNext()){
			Stringline=input.nextLine();
			for(intcolumn=0;column<=line.length()-1;column++){
				charc=line.charAt(column);
				Mazemap[row][column]=c;
			}
			row++;
		}
		for(inti=0;i<12;i++){
			for(intj=0;j<58;j++){
				System.out.print(Mazemap[i][j]);
			}
			System.out.print("
");
		}
		LinkedList<TwoTuple<Integer,Integer>>trace=newLinkedList<TwoTuple<Integer,Integer>>();
		System.out.println(maze(Mazemap,trace));
		System.out.println(trace);
	}

	publicstaticbooleanmaze(char[][]maze,
			List<TwoTuple<Integer,Integer>>trace){
		LinkedList<TwoTuple<Integer,Integer>>path=newLinkedList<TwoTuple<Integer,Integer>>();
		HashSet<TwoTuple<Integer,Integer>>traverse=newHashSet<TwoTuple<Integer,Integer>>();

		for(inti=0;i<maze.length;i++){
			for(intj=0;j<maze[i].length;j++){
				if(maze[i][j]=='S'){
					path.add(newTwoTuple<Integer,Integer>(i,j));
				}
			}
		}
		while(!path.isEmpty()){
			TwoTuple<Integer,Integer>temp=path.pop();

			if(traverse.contains(temp)){
				continue;
			}elseif(maze[temp.first][temp.second]=='F'){
				trace.add(temp);
				returntrue;
			}elseif(!traverse.contains(temp)){
				if(temp.second+1<maze[temp.first].length
						&&maze[temp.first][temp.second+1]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first,
							temp.second+1));
				if(temp.second-1>0
						&&maze[temp.first][temp.second-1]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first,
							temp.second-1));
				if(temp.first+1<maze.length
						&&maze[temp.first+1][temp.second]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first+1,
							temp.second));
				if(temp.first-1>0
						&&maze[temp.first-1][temp.second]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first-1,
							temp.second));
				traverse.add(temp);
				trace.add(temp);
			}
		}
		trace.clear();
		returnfalse;
	}
}

classTwoTuple<A,B>{
	publicfinalAfirst;
	publicfinalBsecond;

	publicTwoTuple(Aa,Bb){
		first=a;
		second=b;
	}

	@Override
	publicinthashCode(){
		returnfirst.hashCode()+second.hashCode();
	}

	@Override
	publicbooleanequals(Objectobj){
		if(!(objinstanceofTwoTuple)){

		}
		returnobjinstanceofTwoTuple&&first.equals(((TwoTuple)obj).first)
				&&second.equals(((TwoTuple)obj).second);
	}

	publicStringtoString(){
		return"("+first+","+second+")";
	}
}///:-



importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.LinkedList;
importjava.util.Scanner;
classMyPoint
{
publicbooleanvisited=false;
publicintparentRow=-1;
publicintparentColumn=-1;
publicfinalcharcontent;
publicintx;
publicinty;
publicMyPoint(charc,intx,inty)
{
		this.content=c;
		this.x=x;
		this.y=y;
}
}
publicclassMaze
{

publicstaticMyPoint[][]getMazeArray(){
		Scannerinput=null;
		MyPoint[][]mazemap=newMyPoint[12][58];
		try{
			input=newScanner(newFile("Maze2tong.txt"));
			introw=0;
			while(input.hasNext()){
				Stringline=input.nextLine();
				for(intcolumn=0;column<=line.length()-1;column++){
					charc=line.charAt(column);
					MyPointpoint=newMyPoint(c,row,column);
					mazemap[row][column]=point;
				}
				row++;
			}
			input.close();
		}catch(FileNotFoundExceptione){
			e.printStackTrace();
		}
		returnmazemap;
}
publicstaticbooleantomRun(MyPoint[][]maze,MyPointend)
{
		intx=maze.length;
		inty=maze[0].length;
		LinkedList<MyPoint>stack=newLinkedList<MyPoint>();
		for(inti=0;i<maze.length;i++){
			for(intj=0;j<maze[i].length;j++){
				if(maze[i][j].content=='S'){
					stack.push(maze[i][j]);
					maze[i][j].visited=true;
				}
			}
		}
booleanresult=false;
while(!stack.isEmpty())
{
MyPointt=stack.pop();
//System.out.println("poppoint:"+t.x+""+t.y+"value:"+maze[t.x][t.y]);
if(t.content=='F')
{
result=true;
end.x=t.x;
end.y=t.y;
break;
}
if(t.x-1>0&&maze[t.x-1][t.y].visited==false&&maze[t.x-1][t.y].content!='W')
{
stack.push(maze[t.x-1][t.y]);
maze[t.x-1][t.y].parentRow=t.x;
maze[t.x-1][t.y].parentColumn=t.y;
maze[t.x-1][t.y].visited=true;
}
if(t.x+1<x&&maze[t.x+1][t.y].visited==false&&maze[t.x+1][t.y].content!='W')
{
stack.push(maze[t.x+1][t.y]);
maze[t.x+1][t.y].parentRow=t.x;
maze[t.x+1][t.y].parentColumn=t.y;
maze[t.x+1][t.y].visited=true;
}
if(t.y-1>0&&maze[t.x][t.y-1].visited==false&&maze[t.x][t.y-1].content!='W')
{
stack.push(maze[t.x][t.y-1]);
maze[t.x][t.y-1].parentRow=t.x;
maze[t.x][t.y-1].parentColumn=t.y;
maze[t.x][t.y-1].visited=true;
}
if(t.y+1<y&&maze[t.x][t.y+1].visited==false&&maze[t.x][t.y+1].content!='W')
{
stack.push(maze[t.x][t.y+1]);
maze[t.x][t.y+1].parentRow=t.x;
maze[t.x][t.y+1].parentColumn=t.y;
maze[t.x][t.y+1].visited=true;
}

}
returnresult;
}
publicstaticvoidshow(intx,inty,MyPoint[][]visited)
{
if(visited[x][y].parentRow==-1)
{
System.out.println("["+x+","+y+"]");
return;
}
show(visited[x][y].parentRow,visited[x][y].parentColumn,visited);
System.out.println("->"+"["+x+","+y+"]");
}
publicstaticvoidmain(String[]args)
{
		MyPoint[][]maze=getMazeArray();
		MyPointpoint=newMyPoint('c',1,1);
if(tomRun(maze,point))
{
System.out.println("逃生路径如下：");
show(point.x,point.y,maze);
}
else
System.out.println("无法走出迷宫！");
}
}

❷ 迷宫最短路径

用堆栈不一定能得出最短路径，改用队列可以实现最短路径，下面是《数据结构算法与应用-C++语言描述》里面的一段话。

[迷宫老鼠] 使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（ 1，2）和（2，1）置为1。

1 1 0
1 1 1
0 0 0
a）

1 1 1
1 1 1
0 0 0
b）

1 1 1
1 1 1
1 0 0
c）

节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有
（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置
为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将
会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，
1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随
后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，
节点（3，1）成为新的E-节点，将队列清空。节点（3，1）展开，（3，2）被加入队列中，而
（3，1）被删除。（3，2）变为新的E-节点，展开此节点后，到达节点（3，3），即迷宫的出口。

使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。

❸ java 最短路径算法如何实现有向任意两点的最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}

MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封装路径距离
Map<String,String> pathInfo=new HashMap<String,String>();//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}

Main用于测试Dijkstra对象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}

❹ 迷宫数组最短路径算法我，我，我给分60！

//对角线也可以走：如从1,3到2,4最短路径为根号2
//如果对角线不想，两个for循环条件判断稍微修改下：
//代码如下：
//输出-1 表示找不到路径
/*
给个数组，0表示通路，1表示阻碍，然后给任意两个0的坐标，可以找到它们之间的最短路径并打印出来
比如说数组是 1 0 0 0 1
1 1 1 0 1
1 1 0 0 1
1 0 0 0 1
1 0 1 1 1
然后我就可以找到第一行第二个数和第五行第二个数之间的最短路径了
*/
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <stdio.h>
#define M 5
#define N 5
typedef struct coordinate{
short int x;
short int y;
} COORDINATE;

COORDINATE path[M*N];//全局变量，存储已访问结点

float getminpath(COORDINATE *,COORDINATE *,char [][N],COORDINATE *);
void main()
{
memset(path,0,sizeof(COORDINATE)*M*N);
char maze[M][N]={
'\1','\0','\0','\0','\1',
'\1','\1','\1','\0','\1',
'\1','\1','\0','\0','\1',
'\1','\0','\0','\0','\1',
'\1','\0','\1','\1','\1',
};
COORDINATE a,b;
float dis;
do{
system("cls");
printf("请输入起点坐标：\n如1,2为第一行第二个数\n");
printf("取值范围1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&a.x,&a.y);

printf("请输入终点坐标：\n如5,2为第五行第二个数\n");
printf("取值范围1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&b.x,&b.y);
a.x--;
a.y--;
b.x--;
b.y--;
dis=getminpath(&a,&b,maze,path);
printf("最短路径为：%f\n",dis);
system("pause");
} while(getchar()!=EOF);
}
float getminpath(COORDINATE *from,COORDINATE *to,char maze[][5],COORDINATE *visited)
//从from结点到to结点可以分成两步，1.从from到from的相邻结点。2.再到to结点，这就是一个递归的过程
//将已访问结点存放入visited中
{
COORDINATE *nearpt=(COORDINATE*)malloc(sizeof(COORDINATE)*1);
memset(nearpt,0,sizeof(COORDINATE));
int i,j;
float min=0;//存储最短路径的值
COORDINATE *pvisit;//遍历已访问结点的指针
char reflag;//相邻结点是否 “已访问” 的flag
float dis=-1;//距离
if(from==0||to==0||maze==0)
{
return -1;
}
else
{
if(from->x==to->x&&from->y==to->y)//坐标相同，表示已到达
{
dis=0;
}
else
{
for(i=-1;i<=1;i++)
{
for(j=-1;j<=1;j++)
{
if(i==0&&j==0)
{
continue;
}
nearpt->x=from->x+i;
nearpt->y=from->y+j;
if(nearpt->x<0||nearpt->x>M-1||nearpt->y<0||nearpt->y>N-1)//越界
{
continue;
}
if(maze[nearpt->x][nearpt->y]!='\0')//非零为障碍，继续下一次循环
{
continue;
}

reflag='\0';//初值为'\0'，表示未访问过
for(pvisit=path;pvisit<visited;pvisit++)//搜索已访问结点
{
if(pvisit->x==nearpt->x&&pvisit->y==nearpt->y)
{
reflag='\1';//该结点已经访问过了
break;
}
}

if(reflag=='\1')
{
continue;
}
else
{
visited->x=from->x;//将from结点加入已访问结点数组中
visited->y=from->y;
dis=getminpath(nearpt,to,maze,visited+1);//递归
if(dis>=0)
{
dis+=sqrt((nearpt->x-from->x)*(nearpt->x-from->x)+(nearpt->y-from->y)*(nearpt->y-from->y));
// printf("%d,%d到%d,%d\t距离：%3f\n",from->x,from->y,to->x,to->y,dis);

if(min==0)//第一次，还没将dis的值赋给m过
{
min=dis;
}
else
{
if(dis<min)
{
min=dis;
}
else
{
}
}
}

visited->x=0;//清除from结点
visited->y=0;
}
}

}
}
}
free(nearpt);
if(min>0)
{
return min;
}
else
{
return dis;
}
}

❺ 跪求迷宫最短路径题目：迷宫最短路径 ⒈问题描述从一个迷宫的入口到出口找出一条最短路经。用一个二维数

擦啊。。。我打了半天字，网络竟然给消了！！尼玛呀！！！
算了，具体算法我不想再写了。楼主去参考下数据结构教材上关于图的最短路径的两种经典算法应该就比较明了了。
我日啊！！！写了10多分钟，网络啊网络！！！

❻ 求用java语言寻找走出迷宫路线的算法

首先给定一个初始坐标，然后构建一个容器保存坐标值，之后进行迭代，横坐标+1，或者纵坐标+1，这个顺寻自己定义（四个方向），经过的“路径”保存在那个容器中，如果遇到死角，以此往回迭代，在容器中将遇到死角的那个坐标删除。最后找到自己定义的那个迷宫出口坐标。

❼ 用java语言求最短路径

最短路径就是敲代码。这个东西行业公认,没有比敲代码学语言更加快的路了。
如果是单纯感兴趣可以买两本书自学什么thinkinjava之类的，开始肯定看不懂的,谁开始都看不懂,摸索着来,时间长了就理解了。如果有其它语言基础学起来就快多了,因为语言这种东西,除了语法不一样,逻辑都是一样的。
如果是工作需要什么的,可以找个培训啥的。当然前提你有钱。
最后顺带吐个槽,捷径好找的话，程序员这工作就不值钱了。

❽ 求java算法源代码求出汽车从起点S出发到达终点T的一条行驶路程最短的路线。

呵呵，你如果最短路径是m*n的这个前提就好算；如果最短不一定是m*n的话就成了一个迷宫问题同样求指点啊

❾ 求java实现矩阵图上任意两点的最短路径源码

我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。

代码欣赏：

publicstaticintstep=1;

=newStringBuffer();

publicstaticint[][]maze={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1},

{1,0,1,0,0,0,1,0,1,1,1},

{1,0,0,0,1,0,1,0,0,0,1},

{1,0,1,1,0,0,1,0,0,1,1},//0代表可以通过，1代表不可通过

{1,0,1,0,1,1,0,1,0,0,1},

{1,0,0,0,0,0,0,0,1,0,1},

{1,0,1,0,1,0,1,0,1,0,1},

{1,0,0,1,0,0,1,0,1,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

publicstaticvoidmain(String[]args){

inti,j;//循环记数变量

Sample.way(1,1);//二维数组起始值从下标1，1开始

System.out.println("起点从坐标x=1,y=1开始");

System.out.println("终点坐标是x=8,y=9结束");

System.out.println("这是迷宫图表");

System.out.println("012345678910");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i=0;i<10;i++){

System.out.print(""+i+"‖");

for(j=0;j<11;j++)

System.out.print("-"+maze[i][j]+"-‖");

System.out.println("");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//打印显示步数

System.out.print(printStep.toString());

}

publicstaticbooleanway(intx,inty){

if(maze[8][9]==2)//代表递归终止条件（也就是当走出出口时标记为2）

returntrue;

else{

if(maze[y][x]==0){

maze[y][x]=2;

*下面if判断条件代表当前坐标为基点，

*根据判断对当前位置进行递归调用：如：

*往上、往右上、往右、往右下、往下、

*往左下、往左、往左上的坐标是否可走，

*判断是否可走的返回条件是：

*2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。

if(way(x,y-1)){