最短路径算法迷宫
⑴ 求一个求从迷宫的一点到另一点的最短路径的递归算法
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++ 迷宫最短路径
一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径
但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码，主要原理是用到
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;
}
⑶ 〔C++算法分析〕迷宫问题
在还没学习bfs的情况下做到一个迷宫问题，于是的大概了解了一下DFS和BFS，就以本题为例子讲一下我初识的bfs
/*
试题 : 迷宫
本题总分：15 分
【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍旁握纤，标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫皮渗的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一运仿共10步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。
在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个字符串，包含四种字母 D、U、L、R，
在提交答案时只填写这个字符串，填写多余的内容将无法得分。
*/
#include
#include
#include
using namespace std;
const int N = 30;
const int M =50; //数据范围
const int fx[4][2] = { 1, 0, 0, -1, 0, 1, -1, 0 }; //方向向量，直接按字典序排列
const char dic[5] = "DLRU"; //字典序
char maze[N+5][M+5]; //地图
char path[N+5][M+5]; //上一步的方向
void bfs()
{
queue > q;
q.push(make_pair(1,1));
maze[1][1]= '1';
while(!q.empty())
{
intx = q.front().first;
inty = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
intxx = x + fx[i][0];
intyy = y + fx[i][1];
if(maze[xx][yy] == '0')
{
maze[xx][yy]= '1';
q.push(make_pair(xx,yy));
path[xx][yy]= i;
}
}
}
}
void print(int x, int y)
{
if(x != 1 || y != 1)
{
intt = path[x][y];
print(x- fx[t][0], y - fx[t][1]);
maze[x][y]= 1; //将走过的地方置1
cout<< dic[t];
}
}
int main()
{
freopen("text.ini","r", stdin);
memset(maze,'1', sizeof maze); //加围墙
for(int i = 1; i <= N; i++)
cin>> maze[i]+1;
bfs();
memset(maze,0, sizeof maze); //初始化，0为墙，1为路径
maze[1][1]= 1;
print(N,M); //输出最短路径字符，同时标记路径为1
//输出迷宫图
cout<< endl;
for(int i = 0; i <= N + 1; i++)
{
for(int j = 0; j <= M + 1; j++)
{
if(i == 0 || i == N + 1 || j == 0 || j == M + 1) cout << "※"; //画围墙
elseif (maze[i][j] == 0) cout << "■"; //迷宫里的墙
elsecout << "□"; //最短路的路径
}
cout<< endl;
}
cout<< "\nover" << endl;
while(1);
return0;
}
事例中，我们先将整个maze数组铺满全部范围，来建立墙，然后再对maze数组赋值，来建立迷宫，从而达到，墙裹着迷宫的效果。
然后我们建立一个名为q的queue来保存我们现在所在的位置。
数组fx代表方向，dic代表方向的字符。
数组path记录上一步的方向
寻路部分
首先将起点放入queue中，取得点之后，让起点出队，在吧起点堵死成墙。
然后从起点获得的值去同时向外延伸，遇到墙不延伸，死路表示这条线终结，没次延伸后，都把原来的点设置成墙。
在延伸的过程中，没到一个点便堵死成墙，并且出队，这样防止一个点多重赋值。
因为是对目前队列里所有的点同时延伸（虽然有先后顺序，但是总会延伸完这一阶段的点才会延伸下一阶段的点），所以不必担心走那条路会早一点到某一点，因为完到的，已经被堵死了。
在将所有起点能到达的点延伸完毕之后，队列为空，进行结算。
如果起点能达到终点的话，终点的path必定有值，只需要在终点倒推即可得到答案。
画图部分
先把全体设置成墙，再按照path倒推，结果是路程全被筛选出来。
by：有我wa
⑷ 李氏迷宫算法的发展
迷宫算法最初是由C．Y．Lee提出的,又称为李氏算法或波扩法，其优点是只要最短路径存在，就一定能找到，然而其缺点也是明显的，对于n×n的网格空间，它需要O（n2）的运行时间和存储空间并产生了较多的层间引线孔。
C.Y.LEE简介:
William C.Y.Lee(威廉．C．Y．李)博士，国际着名科学家，教育家，近代移动通信奠基人之一。
李博士于1963年获得美国Ohio State University电气工程博士学位；1964～1979年，开创了美国贝尔试验室下的移动无线电通信研究室；1979～1985年，任美国ITT公司国防通信部的尖端技术开发部主管；1985～2000年，任美国Vodafone AirTouch公司副总裁和首席科学家。2000～2005年，任美国LinkAir通信公司董事长，现任美国Treyspan公司董事长。
李博士因开发了商用的AMPS和CDMA技术而享誉全世界，在其几十年的科研生涯中，获得殊荣无数。1982年成为IEEE会员，1987年成为全美无线电俱乐部会员，1982～1998年应美国George Washington University邀请，主讲最早的面向产业的蜂窝和移动通信课程。还有ITTDCD的技术贡献奖(1984)，Ohio State University有突出贡献的校友(1990)，IEEE VTSAvant Garde奖(1990)，美国CTIA的奖励证书(1994)，IEEE车载技术协会技术服务奖(1996)，中美(SATEC)杰出贡献证书(1997)以及贝尔试验室致力服务奖(1998)，等等。李博士还是美国国家竞争委员会的会员，美国加利福尼亚州科学技术委员会成员，北京航空航天大学、西南交大的名誉教授。
李博士为蜂窝通信领域作出了巨大的贡献。他的重要专着和教科书《无线与蜂窝通信》(1989年第1版，1997年第2版，本书是2006年第3版的中文版)风靡全球，已被翻译成俄文版、汉语版、日语版、韩语版等多种文字。在该书第1版的序言里，李博士就明确阐述了他为蜂窝通信产业制定的目标：“让我们携起手来，使蜂窝产业发挥它最大的潜力，我们的目标是：在不远的将来，让便携式蜂窝电话把我们的通话遍及世界每一个角落。”
⑸ 如何用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;
}
⑹ 迷宫最短路径
用堆栈不一定能得出最短路径，改用队列可以实现最短路径，下面是《数据结构算法与应用-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搜索，总能找出从迷宫入口到出口的最短路径。
⑺ 迷宫问题（栈或队列，最短路径）（c语言）
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze
[N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze
[N])
{
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto
[N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}