用c语言实现以下功能:用邻接矩阵创建无向网,并用佛洛伊德算法求任一对顶点间的最短路径及路径长度并输出,用迪杰斯特拉算法求出某一顶点到到其他各顶点间的最短路径及路径长度并输出
时间: 2023-11-27 13:53:59 浏览: 73
弗罗伊德算法 求任意两点间最短路径 C语言编的
4星 · 用户满意度95%
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
#define INFINITY 65535
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertices[MAX_VERTEX_NUM]; // 存放顶点信息
int vexnum, arcnum; // 顶点数和边数
} MGraph;
// 创建无向网
void CreateMGraph(MGraph *G) {
int i, j, k, w;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vexnum; ++i) {
scanf("%d", &G->vertices[i]);
}
for (i = 0; i < G->vexnum; ++i) {
for (j = 0; j < G->vexnum; ++j) {
G->arcs[i][j] = INFINITY; // 初始化邻接矩阵
}
}
printf("请输入边的信息:\n");
for (k = 0; k < G->arcnum; ++k) {
scanf("%d%d%d", &i, &j, &w);
G->arcs[i][j] = w;
G->arcs[j][i] = w; // 无向图,对称存储
}
}
// Floyd算法求任一对顶点间的最短路径及路径长度
void Floyd(MGraph *G, int path[][MAX_VERTEX_NUM], int dist[][MAX_VERTEX_NUM]) {
int i, j, k;
for (i = 0; i < G->vexnum; ++i) {
for (j = 0; j < G->vexnum; ++j) {
dist[i][j] = G->arcs[i][j];
path[i][j] = -1;
}
}
for (k = 0; k < G->vexnum; ++k) {
for (i = 0; i < G->vexnum; ++i) {
for (j = 0; j < G->vexnum; ++j) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}
// 迪杰斯特拉算法求某一顶点到其他各顶点间的最短路径及路径长度
void Dijkstra(MGraph *G, int v, int path[], int dist[]) {
int i, j, min, u;
int S[MAX_VERTEX_NUM];
for (i = 0; i < G->vexnum; ++i) {
dist[i] = G->arcs[v][i];
S[i] = 0;
if (G->arcs[v][i] < INFINITY) {
path[i] = v;
} else {
path[i] = -1;
}
}
dist[v] = 0;
S[v] = 1;
for (i = 1; i < G->vexnum; ++i) {
min = INFINITY;
for (j = 0; j < G->vexnum; ++j) {
if (!S[j] && dist[j] < min) {
u = j;
min = dist[j];
}
}
S[u] = 1;
for (j = 0; j < G->vexnum; ++j) {
if (!S[j] && dist[u] + G->arcs[u][j] < dist[j]) {
dist[j] = dist[u] + G->arcs[u][j];
path[j] = u;
}
}
}
}
// 输出任一对顶点间的最短路径及路径长度
void PrintPath(MGraph *G, int path[][MAX_VERTEX_NUM], int dist[][MAX_VERTEX_NUM]) {
int i, j, k;
for (i = 0; i < G->vexnum; ++i) {
for (j = 0; j < G->vexnum; ++j) {
if (i != j) {
printf("%d到%d的最短路径为:", G->vertices[i], G->vertices[j]);
k = path[i][j];
if (k == -1) {
printf("无路径\n");
} else {
printf("%d", G->vertices[i]);
while (k != -1) {
printf("->%d", G->vertices[k]);
k = path[k][j];
}
printf("->%d,长度为:%d\n", G->vertices[j], dist[i][j]);
}
}
}
}
}
// 输出某一顶点到其他各顶点间的最短路径及路径长度
void PrintDijkstra(MGraph *G, int v, int path[], int dist[]) {
int i;
printf("从%d出发到各顶点的最短路径为:\n", G->vertices[v]);
for (i = 0; i < G->vexnum; ++i) {
if (i != v) {
printf("%d到%d的最短路径为:", G->vertices[v], G->vertices[i]);
if (path[i] == -1) {
printf("无路径\n");
} else {
printf("%d", G->vertices[i]);
int j = i;
while (j != v) {
printf("<-%d", G->vertices[path[j]]);
j = path[j];
}
printf("<-%d,长度为:%d\n", G->vertices[v], dist[i]);
}
}
}
}
int main() {
MGraph G;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM], dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int v, path1[MAX_VERTEX_NUM], dist1[MAX_VERTEX_NUM];
CreateMGraph(&G);
Floyd(&G, path, dist);
PrintPath(&G, path, dist);
printf("请输入起点的下标:");
scanf("%d", &v);
Dijkstra(&G, v, path1, dist1);
PrintDijkstra(&G, v, path1, dist1);
return 0;
}
```
注:本代码中使用了邻接矩阵来创建无向网。在Floyd算法中,path数组存放的是中间节点的下标(如果中间节点为-1,则表示i到j之间不存在路径),dist数组存放的是i到j的最短距离。在Dijkstra算法中,path数组存放的是每个顶点的前驱节点的下标(如果前驱节点为-1,则表示从v到该顶点不存在路径),dist数组存放的是从v到每个顶点的最短距离。
阅读全文