用户自定义迷宫地图，指定入口和出口，采用图相关算法寻找一条出入口之间最短路径，c语言，Dijkstra

以下是使用 Dijkstra 算法寻找迷宫地图中最短路径的 C 语言代码实现。假设迷宫地图是一个二维数组 maze，其中0表示通路，1表示障碍物，2表示入口，3表示出口。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define ROWS 5
#define COLS 5

// 定义方向数组，表示四个方向的偏移量
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

// 定义最小堆节点结构体
typedef struct {
    int x;
    int y;
    int dist;
} Node;

// 定义最小堆结构体
typedef struct {
    Node *nodes;
    int size;
    int capacity;
} MinHeap;

// 初始化最小堆
void initHeap(MinHeap *heap) {
    heap->nodes = (Node*) malloc(sizeof(Node) * (ROWS * COLS));
    heap->size = 0;
    heap->capacity = ROWS * COLS;
}

// 交换两个节点
void swapNodes(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 插入一个节点到最小堆中
void insertNode(MinHeap *heap, int x, int y, int dist) {
    if (heap->size == heap->capacity) {
        return; // 堆已满，无法插入新节点
    }
    heap->nodes[heap->size].x = x;
    heap->nodes[heap->size].y = y;
    heap->nodes[heap->size].dist = dist;
    int i = heap->size;
    heap->size++;
    // 将新节点上浮到正确的位置
    while (i > 0 && heap->nodes[i].dist < heap->nodes[(i - 1) / 2].dist) {
        swapNodes(&heap->nodes[i], &heap->nodes[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// 弹出最小堆中的堆顶节点
Node popNode(MinHeap *heap) {
    Node minNode = heap->nodes[0];
    heap->size--;
    // 将最后一个节点移到堆顶，并让它下沉到正确的位置
    heap->nodes[0] = heap->nodes[heap->size];
    int i = 0;
    while (i * 2 + 1 < heap->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int minChild = left;
        if (right < heap->size && heap->nodes[right].dist < heap->nodes[left].dist) {
            minChild = right;
        }
        if (heap->nodes[i].dist > heap->nodes[minChild].dist) {
            swapNodes(&heap->nodes[i], &heap->nodes[minChild]);
            i = minChild;
        } else {
            break;
        }
    }
    return minNode;
}

// 释放最小堆内存
void freeHeap(MinHeap *heap) {
    free(heap->nodes);
    heap->nodes = NULL;
    heap->size = 0;
    heap->capacity = 0;
}

// 计算起点到指定点的距离
int calcDist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// Dijkstra 算法求最短路径
int dijkstra(int maze[ROWS][COLS], int srcX, int srcY, int dstX, int dstY, int (*path)[2]) {
    // 初始化距离数组和visited数组
    int dist[ROWS][COLS];
    int visited[ROWS][COLS];
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            dist[i][j] = INT_MAX; // 初始距离无穷大
            visited[i][j] = 0; // 初始未访问
        }
    }
    dist[srcX][srcY] = 0; // 起点距离为0
    // 初始化最小堆并插入起点
    MinHeap heap;
    initHeap(&heap);
    insertNode(&heap, srcX, srcY, 0);
    // 开始Dijkstra搜索
    while (heap.size > 0) {
        Node node = popNode(&heap); // 取出距离起点最近的节点
        int x = node.x;
        int y = node.y;
        visited[x][y] = 1; // 标记为已访问
        if (x == dstX && y == dstY) {
            // 已找到终点，逆序追踪路径
            int i = dist[dstX][dstY] - 1;
            path[i][0] = dstX;
            path[i][1] = dstY;
            while (i > 0) {
                int minDist = INT_MAX;
                int minx, miny;
                for (int j = 0; j < 4; j++) {
                    int nx = path[i][0] + directions[j][0];
                    int ny = path[i][1] + directions[j][1];
                    if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS && dist[nx][ny] < minDist) {
                        minDist = dist[nx][ny];
                        minx = nx;
                        miny = ny;
                    }
                }
                path[i - 1][0] = minx;
                path[i - 1][1] = miny;
                i--;
            }
            freeHeap(&heap);
            return dist[dstX][dstY]; // 返回最短距离
        }
        // 扩展四个方向的邻居节点
        for (int i = 0; i < 4; i++) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS && !visited[nx][ny] && maze[nx][ny] != 1) {
                int d = calcDist(x, y, nx, ny);
                if (dist[x][y] + d < dist[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + d;
                    insertNode(&heap, nx, ny, dist[nx][ny]);
                }
            }
        }
    }
    freeHeap(&heap);
    return -1; // 没有找到可行路径
}

int main() {
    int maze[ROWS][COLS] = {
        {0, 1, 0, 2, 0},
        {0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 3, 0}
    };
    int path[ROWS * COLS][2];
    int dist = dijkstra(maze, 0, 3, 4, 3, path);
    if (dist >= 0) {
        printf("Shortest distance: %d\n", dist);
        printf("Shortest path: ");
        for (int i = 0; i < dist; i++) {
            printf("(%d, %d) ", path[i][0], path[i][1]);
        }
        printf("\n");
    } else {
        printf("No feasible path.\n");
    }
    return 0;
}

使用上述代码可以找到从入口到出口的最短路径，并输出最短路径的节点坐标以及路径长度。如果没有找到可行的路径，输出无法找到路径的信息。