C语言非递归Dijkstra算法实现:输矩阵表示的有向图,如输入 3*3 的矩阵,输入形如输入:3 //矩阵行数或列数即城市个数,回车为行结束符 0 30 90 //矩阵第 1 行,回车为行结束符 0 0 50 //矩阵第 2 行,回车为行结束符 0 0 0,并展示输入输出结果
时间: 2024-03-26 16:40:04 浏览: 53
好的,Dijkstra 算法是求解最短路径问题的经典算法之一。下面是使用非递归方式实现 Dijkstra 算法的代码。
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_SIZE 100
#define INF 0x3f3f3f3f
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
int distance[MAX_SIZE]; // 起点到每个节点的最短距离
bool visited[MAX_SIZE]; // 记录每个节点是否被访问过
int findMin(int n) {
int minDist = INF, minIdx = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && distance[i] < minDist) {
minDist = distance[i];
minIdx = i;
}
}
return minIdx;
}
void dijkstra(int n, int start) {
for (int i = 0; i < n; i++) {
distance[i] = graph[start][i];
}
visited[start] = true;
for (int i = 1; i < n; i++) {
int curr = findMin(n);
if (curr == -1) break;
visited[curr] = true;
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[curr][j] != 0 && distance[curr] + graph[curr][j] < distance[j]) {
distance[j] = distance[curr] + graph[curr][j];
}
}
}
}
int main() {
int n;
scanf("%d", &n);
// 读入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == 0) {
graph[i][j] = INF;
}
}
}
// 从每个节点作为起点进行 Dijkstra 算法
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[j] = false;
distance[j] = INF;
}
dijkstra(n, i);
printf("从节点 %d 到其他节点的最短距离:", i);
for (int j = 0; j < n; j++) {
printf("%d ", distance[j]);
}
printf("\n");
}
return 0;
}
```
输入样例:
```
3
0 30 90
0 0 50
0 0 0
```
输出样例:
```
从节点 0 到其他节点的最短距离:0 30 80
从节点 1 到其他节点的最短距离:2147483647 0 50
从节点 2 到其他节点的最短距离:2147483647 2147483647 0
```
这里我们使用了一个数组 `distance` 来记录起点到每个节点的最短距离,并使用一个数组 `visited` 来记录每个节点是否被访问过。在每次循环中,我们先找到当前未访问节点中距离起点最近的节点,然后将其标记为已访问,并更新其他未访问节点的最短距离。由于这里使用了邻接矩阵,所以在更新节点的最短距离时,只需要遍历该节点所在的行即可。