C语言用迪杰特斯拉算法寻矩形迷宫最短路径，附代码及样例

```c #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 int maze[MAX_SIZE][MAX_SIZE]; int visited[MAX_SIZE][MAX_SIZE]; int path[MAX_SIZE][2]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int minDistance(int dist[], int n) { int min = INT_MAX, min_index; for (int i = 0; i < n; i++) { if (visited[i] == 0 && dist[i] <= min) { min = dist[i]; min_index = i; } } return min_index; } int printPath(int path[][2], int size) { for (int i = 0; i < size; i++) { printf("%d %d\n", path[i][0], path[i][1]); } } void dijkstra(int n, int m) { int dist[n * m]; for (int i = 0; i < n * m; i++) { dist[i] = INT_MAX; visited[i] = 0; } int start_x, start_y; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (maze[i][j] == 3) { start_x = i; start_y = j; break; } } } dist[start_x * m + start_y] = 0; for (int i = 0; i < n * m; i++) { int u = minDistance(dist, n * m); visited[u] = 1; int x = u / m; int y = u % m; for (int j = 0; j < 4; j++) { int new_x = x + dx[j]; int new_y = y + dy[j]; if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && maze[new_x][new_y] != 0 && visited[new_x * m + new_y] == 0) { if (dist[u] + 1 < dist[new_x * m + new_y]) { dist[new_x * m + new_y] = dist[u] + 1; path[dist[new_x * m + new_y] - 1][0] = new_x; path[dist[new_x * m + new_y] - 1][1] = new_y; } } } } int end_x, end_y; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (maze[i][j] == 4) { end_x = i; end_y = j; break; } } } int x = end_x, y = end_y, k = 0; while (x != start_x || y != start_y) { path[k][0] = x; path[k][1] = y; int min_dist = INT_MAX; int next_x, next_y; for (int j = 0; j < 4; j++) { int new_x = x + dx[j]; int new_y = y + dy[j]; if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && maze[new_x][new_y] != 0 && visited[new_x * m + new_y] == 1 && dist[new_x * m + new_y] < min_dist) { min_dist = dist[new_x * m + new_y]; next_x = new_x; next_y = new_y; } } x = next_x; y = next_y; k++; } path[k][0] = x; path[k][1] = y; printPath(path, k + 1); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &maze[i][j]); } } dijkstra(n, m); return 0; } ``` 运行该程序，输入矩阵大小和矩阵中的元素，即可输出从入口到出口的最短路径上的每一个点的位置。 ######[AI写代码神器 | 2036点数解答 | 2024-12-16 22:29:21]