深度优先搜索的最短路径问题

这个简单的图，要求使用深度优先算法求出（1,1）到终点的最短路径。

1、分析

就目前看来，(1,1)->(1,2)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)和(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3)这两条路径是相同的长度的最短路劲。但是，这是我们的肉眼看到的，如果是计算机计算，他需要计算每个步骤的方向，每个方向的尝试，直到无路可走或者到达终点。

2、尝试

尝试用深度优先搜索来实现这个方法。先来看dfs函数如何写。上面讲到dfs()函数的功能是解决当前应该怎么办。假设初始点到达每个位置，需要处理的是：先检查“点”是否到达终点，如果没有达到则找出下一步可以走的地方。为了解决这个问题，此处dfs()函数只需要维护3个参数，分别是当前这个点的x坐标、y坐标以及当前已经走过的步数step。
此时dfs()函数定义如下。

void dfs(int x, int y, int step)
{
    return;
}

判断是否到达终点，只需要判断此时的点和终点是否相等就行。

void dfs(int x, int y, int step)
{
    // 判断是否到达终点
    if (x == p && y == q)
    {
        // 更新最小值
        if (step < min)
            min = step;
        return; // 请注意这里的返回很重要
    }

    return;
}

如果没有到达，就找到下一步可以走的地方。因为有四个方向可以总，这里按照顺时针的方向来尝试(即按照右、下、左、上的顺序)。定义一个next方向数组。

int next[4][2] = {
    {0, 1},  // 向右走
    {1, 0},  // 向下走
    {0, -1}, // 向左走
    {-1, 0}  // 向上走
};

通过这个方向数组，使用循环获得下一步的坐标。横坐标用tx，纵坐标用ty。

for (k = 0; k <= 3; k++)
{
    // 计算的下一个点的坐标
    tx = x + next[k][0];
    ty = y + next[k][1];
}

接下来我们需要判断下一个点（tx,ty），是否越界，是否为障碍物，以及这个点是否已在路径中。需要用book[tx][ty]来记录格子(tx,ty)是否已经在路径中。
如果这个点符号所有要求，就进行下一次扩展，即dfs(tx,ty,step+1)，注意这里是step+1，每个点的向下尝试，意味着你的步数已经增加 1 。
代码实现如下：

for (k = 0; k <= 3; k++)
{
    // 计算的下一个点的坐标
    tx = x + next[k][0];
    ty = y + next[k][1];

    // 判断是否越界
    if (tx < 1 || tx > n || ty < 1 || ty > m)
        continue;
    // 判断该点是否为障碍物或者已经在路径中

    if (a[tx][ty] == 0 && book[tx][ty] == 0)
    {
        book[tx][ty] = 1;      // 标记这个点已经走过
        dfs(tx, ty, step + 1); // 开始尝试下一个点
        book[tx][ty] = 0;      // 尝试结束，取消这个点的标记
    }
}

分析完毕，代码实现：

#include <stdio.h>
int n, m, p, q, min = 99999999;
int a[51][51], book[51][51];
void dfs(int x, int y, int step)
{
    int next[4][2] = {
        {0, 1},  // 向右走
        {1, 0},  // 向下走
        {0, -1}, // 向左走
        {-1, 0}  // 向上走
    };
    int tx, ty, k;
    // 判断点的位置
    // 判断是否到达终点
    if (x == p && y == q)
    {
        // 更新最小值
        if (step < min)
            min = step;
        return; // 请注意这里的返回很重要
    }
    for (k = 0; k <= 3; k++)
    {
        // 计算的下一个点的坐标
        tx = x + next[k][0];
        ty = y + next[k][1];

        // 判断是否越界
        if (tx < 1 || tx > n || ty < 1 || ty > m)
            continue;
        // 判断该点是否为障碍物或者已经在路径中
        if (a[tx][ty] == 0 && book[tx][ty] == 0)
        {
            book[tx][ty] = 1;      // 标记这个点已经走过
            dfs(tx, ty, step + 1); // 开始尝试下一个点
            book[tx][ty] = 0;      // 尝试结束，取消这个点的标记
        }
    }
    return;
}
int main()
{
    int i, j, startx, starty;
    // 读入n和m，n为行，m为列
    scanf("%d %d", &n, &m);
    // 读入迷宫
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            scanf("%d",&a[i][j]);
    // 读入起点和终点坐标
    scanf("%d %d %d %d", &startx, &starty, &p, &q);
    // 从起点开始搜索
    book[startx][starty] = 1; // 标记点已经在路径中，防止后面重复走
    // 第一个参数是起点的x的坐标，第二个参数是起点的y坐标，第三个参数是初始步数0
    dfs(startx, starty, 0);
    // 输出最短步数
    printf("%d", min);
    getchar();
    getchar();
    return 0;
}

可以输入以下数据验证。

运行结果