C语言非递归算法实现:输矩阵表示的有向图,如输入 3*3 的矩阵,输入形如输入:3 //矩阵行数或列数即城市个数,回车为行结束符 0 30 90 //矩阵第 1 行,回车为行结束符 0 0 50 //矩阵第 2 行,回车为行结束符 0 0 0 //矩阵第 3 行,回车为行结束符输出:A B,30 //A 到 B 的最短路径,路径长度 30 A B C,80 //A 到 C 的最短路径,路径长度 80
时间: 2024-01-21 10:02:09 浏览: 46
好的,这是一个经典的求有向图最短路径的问题。我可以给你提供一个基于Dijkstra算法的C语言非递归实现,如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定义图的最大节点数
#define MAX_NODES 100
// 定义节点结构体
typedef struct node {
int index;
int dist;
int visited;
struct node *next;
} Node;
// 定义图结构体
typedef struct graph {
int num_nodes;
Node *nodes[MAX_NODES];
} Graph;
// 初始化图
void init_graph(Graph *g, int n) {
g->num_nodes = n;
for (int i = 0; i < n; i++) {
g->nodes[i] = (Node *)malloc(sizeof(Node));
g->nodes[i]->index = i;
g->nodes[i]->dist = INT_MAX;
g->nodes[i]->visited = 0;
g->nodes[i]->next = NULL;
}
}
// 添加边
void add_edge(Graph *g, int u, int v, int w) {
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->index = v;
new_node->dist = w;
new_node->visited = 0;
new_node->next = g->nodes[u]->next;
g->nodes[u]->next = new_node;
}
// Dijkstra算法
void dijkstra(Graph *g, int start, int end) {
// 初始化起点的距离为0
g->nodes[start]->dist = 0;
// 遍历所有节点
for (int i = 0; i < g->num_nodes; i++) {
// 找到当前未访问节点中距离最小的节点
int min_dist = INT_MAX;
int min_index = -1;
for (int j = 0; j < g->num_nodes; j++) {
if (!g->nodes[j]->visited && g->nodes[j]->dist < min_dist) {
min_dist = g->nodes[j]->dist;
min_index = j;
}
}
// 如果找不到未访问节点,退出循环
if (min_index == -1) {
break;
}
// 标记当前节点为已访问
g->nodes[min_index]->visited = 1;
// 更新当前节点的邻居节点的距离
Node *p = g->nodes[min_index]->next;
while (p != NULL) {
if (!g->nodes[p->index]->visited && g->nodes[min_index]->dist + p->dist < g->nodes[p->index]->dist) {
g->nodes[p->index]->dist = g->nodes[min_index]->dist + p->dist;
}
p = p->next;
}
}
// 输出最短路径
printf("%c", start + 'A');
int curr = end;
while (curr != start) {
Node *p = g->nodes[curr]->next;
while (p != NULL) {
if (g->nodes[p->index]->dist + p->dist == g->nodes[curr]->dist) {
printf(" %c", p->index + 'A');
curr = p->index;
break;
}
p = p->next;
}
}
printf(",%d\n", g->nodes[end]->dist);
}
int main() {
int n;
scanf("%d", &n);
Graph g;
init_graph(&g, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int w;
scanf("%d", &w);
if (w != 0) {
add_edge(&g, i, j, w);
}
}
}
char start, end;
scanf(" %c %c", &start, &end);
dijkstra(&g, start - 'A', end - 'A');
return 0;
}
```
你可以按照输入格式输入矩阵表示的有向图,然后输入起点和终点,程序会输出起点到终点的最短路径和路径长度。需要注意的是,这个程序假设节点用大写字母表示,且节点数不超过100。