迷宫最短路径算法
Ⅰ 挑战程序设计竞赛上的问题，迷宫的最短路径
typedefpair<int,int>p;
这就是p的定义啊，p是一个类型
至于 pair 还是学一下比较好，很常用的。
pair 的定义大概是这样：
template<class_T1,class_T2>
structpair
{
_T1first;
_T2second;
//....
}
Ⅱ 迷宫最短路径
用堆栈不一定能得出最短路径，改用队列可以实现最短路径，下面是《数据结构算法与应用-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搜索，总能找出从迷宫入口到出口的最短路径。
Ⅲ 求一个求从迷宫的一点到另一点的最短路径的递归算法
typedef struct node
{
int i;
struct node **nearby;//相邻结点可以有多个，所以这里用指针的指针
} MAPNODE;
MAPNODE a,b;
int minpath(a,b)//从a结点到b结点可以分成两步，1.从a到b的相邻结点。2.从相邻结点到b结点，这就是一个递归的过程
{
int dis=0;
int min=999999;//一个足够大的数据
MAPNODE **p;
if(a.i==b.i)//序号相同表示是同一结点，path为0
{
dis=0;
}
else
{
for(p=b.nearby;*p!=0;p++)
{
dis=0;
dis+=minpath(a,*p);
dis<min?min=dis:;
}
}
return dis;
}
Ⅳ 如何用C语言实现求迷宫的最短路径
#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫，0表示能走的块，1表示不能走，在外围加上一圈不能走的块
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //块的位置
int pre; //本路径中上一块在队列中的下标
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循环
}
}
}
return 0;
}
void print(int n) //输出 路径算法
{
int k=n,j,m=1;
printf("\n");
do //将输出的路径上的所有pre改为-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宫最短路径如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}
Ⅳ 迷宫数组 最短路径算法 我， 我， 我给分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;
}
}
Ⅵ 迷宫探路III（最短路径）
/* 迷宫探路III（最短路径）*/
/* DIJKSTRAMAZE.C */
/* 2003-8-26 */
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>
#define N 22
#define M 22
int bg[M][N];
int aa[M][N];
struct pace{
int pre;
int x;
int y;
int ri;
int rj;
}road[M*N];
struct pace bestroad[M*N];
void makebg(int,int);
void drawbg(int[][],int,int,int,int,int);
void drawman(int,int,int);
void rect(int,int,int,int);
void main(){/* main()开始 */
int step=20;
int len=10;
int size=20;
int x=0,y=0;
int i=0,j=0;
int gdriver=DETECT,gmode;
char ch;
int direc;
int routelen=0;
int dj[]={-1,1,0,0};
int di[]={0,0,-1,1};
int begin;
int end;
int k;
int t;
int num;
int suc;
int cnt;
int x0;
int y0;
int le;
int tmp;
makebg(M,N);
/* registerbgidriver(EGAVGA_driver);
initgraph(&gdriver,&gmode,"c:\\turboc2");*/
initgraph(&gdriver,&gmode,"c:\\tc20\\bgi");
cleardevice();
setwritemode(XOR_PUT);
settextstyle(1,0,3);
setcolor(GREEN);
outtextxy(100,180,"DIJKSTRA MAZE");
setcolor(BLUE);
setfillstyle(LINE_FILL,BLUE);
/*drawbg(bg,M,N,size,0,0);*/
drawbg(aa,M,N,size,0,0);
setcolor(WHITE);
x+=len;y+=len;
drawman(x,y,len);
x0=x;y0=y;
/* 电脑控制 */
i=j=0;
aa[0][0]=1;
begin=0;
end=0;
road[0].ri=0;
road[0].rj=0;
road[0].x=x0;
road[0].y=y0;
road[0].pre=-1;
le=1;
suc=0;
while(!suc){
cnt=0;
le++;
for(k=begin;k<=end;k++){
for(t=0;t<4;t++){
x=road[k].x+dj[t]*step;
y=road[k].y+di[t]*step ;
i=road[k].ri+di[t];
j=road[k].rj+dj[t];
if(i<M&&i>=0&&j<N&&j>=0&&aa[i][j]==0){
cnt++;
aa[i][j]=le;
road[end+cnt].pre=k;
road[end+cnt].x=x;
road[end+cnt].y=y;
road[end+cnt].ri=i;
road[end+cnt].rj=j;
if(i==N-1&&j==M-1){
suc=1;
break;
}
}
}
if(suc)break;
}
begin=end+1;
end=end+cnt;
}
/* output */
i=end;j=0;
while(i!=-1){
bestroad[j].x=road[i].x;
bestroad[j].y=road[i].y;
bestroad[j].ri=road[i].ri;
bestroad[j].rj=road[i].rj;
i=road[i].pre;
j++;
}
for(i=0;i<j/2;i++){
tmp=bestroad[i].x;
bestroad[i].x=bestroad[j-1-i].x;
bestroad[j-1-i].x=tmp;
tmp=bestroad[i].y;
bestroad[i].y=bestroad[j-1-i].y;
bestroad[j-1-i].y=tmp;
}
getch();
drawman(x0,y0,len);
for(i=0;i<j;i++){
drawman(bestroad[i].x,bestroad[i].y,len);
delay(80000);
drawman(bestroad[i].x,bestroad[i].y,len);
}
i--;
drawman(bestroad[i].y,bestroad[i].x,len);
getch();
closegraph();
Ⅶ 数据结构算法 用C++ 迷宫最短路径
一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径
但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码，主要原理是用到
quei，quej和prep三个数组来构成队列
分别储存路径的行，列坐标和上一个节点在队列中的位置
大致算法如下，右三个嵌套的循环实现
首先是第一个节点进入队列
当队列不空（循环1）
｛
遍历队列中每节点(循环2）
｛
将八个方向能够走的节点加入队列（循环3）
｝
旧的节点出列
｝
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"请输入迷宫大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩阵中1的个数，太多1迷宫很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是输入和迷宫生成，一下是走迷宫
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//储存行坐标队列
int*quej=newint[m*n];//储存列坐标队列
int*prep=newint[m*n];//储存之前一步在队列中的位置
inthead,rear,length;//队列头，队列尾，队列长度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列
intpos;//当前节点在队列中的位置，
intii,jj,ni,nj;//当前节点的坐标，新节点的坐标
intdir;//移动方向
if(maze[1][1]==1)length=0;//第一点就不能通过
elsemaze[1][1]=1;
while(length)//队列非空继续
{
for(pos=head;pos<head+length;pos++)//寻找这一层所有节点
{
ii=quei[pos];jj=quej[pos];//当前位置坐标
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//寻找8个方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标
if(maze[ni][nj]==0)//如果没有走过
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
rear=rear+1;
maze[ni][nj]=1;//标记已经走过
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//这一层节点出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
Ⅷ 迷宫最短路径算法，时间复杂度最低的是那种
http://..com/question/24452924.html?si=5
Ⅸ 怎样求得迷宫中的的最短路径
建议采用双向广度优先搜索算法，对于迷宫问题貌似是最高效的算法了
Ⅹ 用图论做一个求迷宫最短路径的算法
以起点为首节点开始分支，分支的个数就是当前节点有几个位置可以走，节点内容为当前所在迷宫位置
就这样不停的分支，每生成一个节点就判断是否为终点位置，是则得出结果，
输出路径。因为生成的树的层数对应的正是已走的步数，所以第一个结果必是最短的
另外在数据结构上可以多设计一个数组记录已经走过的位置，当生成的节点位置已经被走过，则可删除该节点，
这样可以减少搜索次数。
这是类似的广度搜索，如果数据量不多，用递归会更直观，简单。