c語言求迷宮最短路徑的演算法代碼

㈠ 如何用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[M][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還是不錯滴
}
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[M][N])
{
int i,j;
int m,n; //迷宮行,列 [/M]

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("你建立的迷宮為(最外圈為強)...\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[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北 [/M]

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");
}

㈡ 求c語言最短路徑演算法

#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

// 各數組都從下標1開始
int dist[maxnum]; // 表示當前點到源點的最短路徑長度
int prev[maxnum]; // 記錄當前點的前一個結點
int c[maxnum][maxnum]; // 記錄圖的兩點間路徑長度
int n, line; // 圖的結點數和路徑數

// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判斷是否已存入該點到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用過該點
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;

// 依次將未放入S集合的結點中，取dist[]最小值的結點，放入結合S中
// 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度
// 注意是從第二個節點開始，第一個為源點
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出當前未使用的點j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存當前鄰接點中距離最小的點的號碼
tmp = dist[j];
}
s[u] = 1; // 表示u點已存入S集合中

// 更新dist
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

// 查找從源點v到終點u的路徑，並輸出
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}

int main()
{
freopen("input.txt", "r", stdin);
// 各數組都從下標1開始

// 輸入結點數
cin >> n;
// 輸入路徑數
cin >> line;
int p, q, len; // 輸入p, q兩點及其路徑長度

// 初始化c[][]為maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;

for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重邊
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p，這樣表示無向圖
}
}

for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("
");
}

Dijkstra(n, 1, dist, prev, c);

// 最短路徑長度
cout << "源點到最後一個頂點的最短路徑長度: " << dist[n] << endl;

// 路徑
cout << "源點到最後一個頂點的路徑為: ";
searchPath(prev, 1, n);
}

㈢ c語言版數據結構，要求用隊列求解迷宮最短路徑。

// Migong_Queue.cpp : 定義控制台應用程序的入口點。

#include "stdafx.h"
#include "stdlib.h"
#define MaxSize 100
struct
{
int i,j;
int pre;
}Qu[MaxSize];
int front = -1,rear = -1;

int mgpath(int **,int ,int ,int ,int);
void print(int);
int _tmain(int argc, _TCHAR* argv[])
{
int l,h;
FILE *migong=fopen("C:\\Users\\Administrator\\Documents\\Visual Studio 2010\\Projects\\數據結構實驗\\Migong_Queue\\migong.txt","r");
if(migong==NULL)
{
printf("Can't open the file!!!");
exit(0);
}
char ch=fgetc(migong);
l=0;
while(ch!='\n')
{
if(ch!=',')
l++;
ch=fgetc(migong);
}//l為迷宮的長度
rewind(migong);
//接下來是算出迷宮的高度h！~~
h=0;
ch=fgetc(migong);
while(!feof(migong))
{
if(ch=='\n')
h++;
ch=fgetc(migong);
}

if(l<5||h<5)
{
printf("It's too small!");
exit(0);
}
rewind(migong);

int **mg=(int **)malloc(sizeof(int *)*h);
for(int h_=0;h_<h;h_++)
{
mg[h_]=(int *)malloc(sizeof(int)*l);
}
for(int h_=0;h_<h;h_++)
{
for(int l_=0;l_<l;)
{
ch=fgetc(migong);
if(ch!=',')
{mg[h_][l_]=ch-'0';l_++;}

}
ch=fgetc(migong);
}
fclose(migong);

printf("The map is presented as follows:\n");
for(int _x=0;_x<h;_x++)
for(int _y=0;_y<l;_y++)
{
printf("%d ",mg[_x][_y]);
if((_y+1)%l==0)
printf("\n");
}
mgpath(mg,1,1,8,8);
return 0;
}
int mgpath(int **mg,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[xi][yi]=-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 front)
{
int k=front,j,ns=0;
printf("\n");
do
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮路徑如下：\n");
k=0;
while(k<MaxSize)
{
if(Qu[k].pre==-1)
{
ns++;
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(ns%5==0)printf("\n");
}
k++;
}
printf("\n");
}

我是從文件中讀取迷宮數組的！
你也可以改為直接輸入！
希望對你有幫助！謝謝！

㈣ 迷宮問題（棧或隊列，最短路徑）（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");
}