用图论做一个求迷宫最短路径的算法？

用图论做一个求迷宫最短路径的算法？

以起点为首节点开始分支，分支的个数就是当前节点有几个位置可以走，节点内容为当前所在迷宫位置
就这样不停的分支，每生成一个节点就判断是否为终点位置，是则得出结果，
输出路径。因为生成的树的层数对应的正是已走的步数，所以第一个结果必是最短的
另外在数据结构上可以多设计一个数组记录已经走过的位置，当生成的节点位置已经被走过，则可删除该节点，
这样可以减少搜索次数。
这是类似的广度搜索，如果数据量不多，用递归会更直观，简单。

#define MAXLEN 1000
#define VERTEXNUM 6
#define INFINITE 1000
#include
int cost[7][7];
int dist[7];
int selected[7];
int normal = 0, Recursion = 0;
void creategraph(int *node, int num)
{
int from, to, i;
for (i=0; i {
from = node[i*3];
to = node[i*3+1];
cost[from][to] = node[i*3+2];
}
}
void Dijkstra(int begin, int num)
{
int min, s, i, j;
for (i=2; i<=num; i++)
{
selected[i] = 0;
dist[i] = cost[begin][i];
}
selected[begin] = 1;
dist[begin] = 0;
for (j=1; j<=num; j++)
printf("%4d ", dist[j]);
printf("\n");
for (i=1; i {
min = MAXLEN;
for (j=1; j<=num; j++)
if ((min>dist[j]) && (selected[j]==0))
{
s = j;
min = dist[j];
normal++;
}
selected[s] = 1;
for (j=1; j<=num; j++)
{
if ((selected[j] == 0) && ((dist[s]+cost[s][j]) {
dist[j] = dist[s] + cost[s][j];
normal++;
}
printf("%4d ", dist[j]);
}
printf("\n");
}
}
void initializtion(int *node, int num)
{
int from, to, i, j;
for (i=1; i<7; i++)
for (j=1; j<7; j++)
{
cost[i][j] = INFINITE;
if (i == j) cost[i][j] = 0;
}
for (i=1; i<7; i++)
{
dist[i] = INFINITE;
selected[i] = 0;
}
for (i=0; i {
from = node[i*3];
to = node[i*3+1];
cost[from][to] = node[i*3+2];
}
}
void DijkstraRecursion(int No)
{
int s, i, min, flag;

min = MAXLEN;
selected[No] = 1;
flag = 0;
for (i=1; i<7; i++)
{
if ((cost[No][i]!=-1) && ((dist[No]+cost[No][i]){
dist[i] = dist[No] + cost[No][i];
Recursion++;
}
if ((selected[i] == 0) && (min>dist[i]))
{
s = i;
min = dist[i];
flag = 1;
Recursion++;
}
}
if (flag == 1)
DijkstraRecursion(s);
else
return;
}
void SelectFirst(int No)
{
dist[No] = 0;
DijkstraRecursion(No);
}
void main()
{
int node[7][3] = {
{1, 2, 35},
{2, 3, 45},
{2, 4, 30},
{3, 5, 25},
{4, 5, 45},
{4, 6, 130},
{5, 6, 100}
};
int i, j;
for (i=1; i<7; i++)
for (j=1; j<7; j++)
cost[i][j] = MAXLEN;
creategraph((int *)node, 7);
printf("...\n");
for (i=1; i<=6; i++)
{
for (j=1; j<=6; j++)
printf("%4d ", cost[i][j]);
printf("\n");
}
printf("...\n");
Dijkstra(1, 6);
printf("...\n");
initializtion((int *)node, 7);
SelectFirst(2);
for (i=1; i<7; i++)
printf("%4d ", dist[i]);
printf("\n");
printf("normal=%d Recursion=%d\n", normal, Recursion);
}