使用C的二维数组中的最短路径

Question

我想找到从 (0,0) 到 (6,6) 的最短路径，但我不知道如何使用 C 来实现。-1 是我可以走的路，-2 是我不能走的路。 0 是起点，-3 是终点。请帮忙..

#include<stdio.h>

#define VERTICES 7

int maze[VERTICES][VERTICES] = {
{  0, -2, -1, -1, -1, -1, -1 },
{ -1, -2, -1, -2, -2, -2, -2 },
{ -1, -1, -1, -1, -1, -1, -1 },
{ -1, -2, -2, -2, -2, -2, -1 },
{ -1, -2, -1, -1, -1, -2, -1 },
{ -1, -2, -1, -2, -2, -2, -1 },
{ -1, -1, -1, -2, -1, -1, -3 } };

int A[VERTICES][VERTICES];

printA(int n)
{
int i, j;
printf("===============================\n");
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++)
        printf("%3d", A[i][j]);
    printf("\n");
}
printf("===============================\n");
}
void solve(int n)
{
int i, j, k=0;
for (i = 0; i<n; i++)
    for (j = 0; j<n; j++)
        A[i][j] = maze[i][j];

while (1)
{
    for (i = 0; i < n; i++)
    {   
        for (j = 0; j < n; j++)
            if (A[i][j] == k)
            {
                if (0 <= i + 1 < n && 0 <= j < n && A[i + 1][j] == -1)
                    A[i + 1][j] = k + 1;
                if (0 <= i - 1 < n && 0 <= j < n && A[i - 1][j] == -1)
                    A[i - 1][j] = k + 1;
                if (0 <= i < n && 0 <= j + 1 < n && A[i][j + 1] == -1)
                    A[i][j + 1] = k + 1;
                if (0 <= i < n && 0 <= j - 1 < n && A[i][j - 1] == -1)
                    A[i][j - 1] = k + 1;
                if (A[i][j] == -3)
                    break;
            }
    }
    k++;
}
printf("%d\n", k);
printA(VERTICES);
}

main()
{
solve(VERTICES);
}

Answer 1

我知道，这应该是一个表扬，但我没有足够的声誉..无论如何：

您也可以寻找 a*（a-star）算法来解决您的问题，这里有大量可用的实现和描述，例如：

http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/

http://www.codeproject.com/Articles/9880/Very-simple-A-algorithm-implementation

heyes-jones.com/astar.php

Answer 2

正如 Jan Raufelder 所建议的，您可以使用 A* 算法，它是速度和准确性之间的最佳折衷方案，广泛用于视频游戏。然而，有些情况下 A* 会在相当长的时间后交付最短路径，而这些最坏情况的场景大多出现在迷宫中。

███████████████████████  In this case,
██ S       1 ██ E    ██  A* will start at S,
██   █████████████   ██  explore branch 1,
██            2 ██   ██  then branch 2,
██   █████████████   ██  and then branch 3,
██            3 ██   ██  before taking branch 4
██   █████████████   ██  to finally get to E.
██            4      ██  It still gives you the shortest path,
███████████████████████  but it takes a huge time.

如果您想要更稳健且通常更快的解决方案，您可以尝试将迷宫转换为图形（顶点和边），并对其应用 Dijkstra 算法。但这意味着你要重做到目前为止所做的一切，并花一些时间考虑如何在内存中构建你的迷宫，因为它不仅仅是 int.[= 的二维数组。 12=]

使用C的二维数组中的最短路径

shortest path in two-dimensional array using C

c

shortest-path