C语言实现Dijkstra算法求解景点最短路径

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

#define MAX_NAME_LEN 20 // 定义景点名称最大长度 #define MAX_VERTEX_NUM 20 // 定义最大景点数 #define INFINITY 65535 // 定义无穷大距离

typedef struct { char name[MAX_NAME_LEN]; // 景点名称 int x; // x坐标 int y; // y坐标 } VertexType;

typedef struct { int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边的权重 int vexnum; // 顶点数 int arcnum; // 边数 VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息 } MGraph;

// 初始化图 void InitGraph(MGraph *G) { int i, j; G->vexnum = 10; // 假设有10个景点 G->arcnum = 15; // 假设有15条路径 // 初始化边的权重 for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->edges[i][j] = INFINITY; // 初始化为无穷大 } } // 添加边的权重 G->edges[0][1] = G->edges[1][0] = 500; G->edges[0][2] = G->edges[2][0] = 1000; G->edges[0][3] = G->edges[3][0] = 800; G->edges[1][2] = G->edges[2][1] = 400; G->edges[1][4] = G->edges[4][1] = 700; G->edges[2][3] = G->edges[3][2] = 600; G->edges[2][4] = G->edges[4][2] = 500; G->edges[2][5] = G->edges[5][2] = 900; G->edges[3][5] = G->edges[5][3] = 600; G->edges[4][5] = G->edges[5][4] = 800; G->edges[4][6] = G->edges[6][4] = 400; G->edges[5][7] = G->edges[7][5] = 300; G->edges[5][8] = G->edges[8][5] = 700; G->edges[6][7] = G->edges[7][6] = 500; G->edges[7][8] = G->edges[8][7] = 400; }

// 查找景点编号 int LocateVex(MGraph G, char name[]) { int i; for (i = 0; i < G.vexnum; i++) { if (strcmp(name, G.vexs[i].name) == 0) { return i; } } return -1; }

// Dijkstra算法求最短路径 void Dijkstra(MGraph G, int v0, int dist[], int path[]) { int i, j, k, min; int final[MAX_VERTEX_NUM] = {0}; // 表示是否已找到最短路径 // 初始化距离和路径 for (i = 0; i < G.vexnum; i++) { dist[i] = G.edges[v0][i]; if (G.edges[v0][i] < INFINITY) { path[i] = v0; } else { path[i] = -1; } } dist[v0] = 0; final[v0] = 1; // 循环n-1次，每次找到一个最短路径 for (i = 1; i < G.vexnum; i++) { min = INFINITY; // 找到未找到最短路径的点中距离最短的点 for (j = 0; j < G.vexnum; j++) { if (!final[j] && dist[j] < min) { min = dist[j]; k = j; } } final[k] = 1; // 更新其他点的距离和路径 for (j = 0; j < G.vexnum; j++) { if (!final[j] && (min + G.edges[k][j] < dist[j])) { dist[j] = min + G.edges[k][j]; path[j] = k; } } } }

// 输出最短路径 void PrintPath(MGraph G, int v0, int v1, int path[]) { int i, j, k; int shortPath[MAX_VERTEX_NUM]; int len = 0; // 找到最短路径 k = v1; while (k != v0) { shortPath[len++] = k; k = path[k]; } shortPath[len++] = v0; // 输出最短路径 printf("最短路径为："); for (i = len - 1; i >= 0; i--) { j = shortPath[i]; printf("%s", G.vexs[j].name); if (i > 0) { printf("->"); } } printf("\n"); }

int main() { MGraph G; int dist[MAX_VERTEX_NUM]; // 存储最短距离 int path[MAX_VERTEX_NUM]; // 存储最短路径 char start[MAX_NAME_LEN], end[MAX_NAME_LEN]; int v0, v1; // 初始化图 InitGraph(&G); // 获取起点和终点 printf("请输入起点："); scanf("%s", start); printf("请输入终点："); scanf("%s", end); v0 = LocateVex(G, start); v1 = LocateVex(G, end); if (v0 == -1 || v1 == -1) { printf("输入的景点名称有误！\n"); return 0; } // 使用Dijkstra算法计算最短路径 Dijkstra(G, v0, dist, path); // 输出最短路径 PrintPath(G, v0, v1, path); return 0; }

如何输入运行内容：可以使用命令行或者集成开发环境（IDE）来运行该程序。

在命令行中输入以下命令：

编译程序

gcc -o shortest_path shortest_path.c

运行程序

./shortest_path

在程序运行后，按照提示输入起点和终点即可得到最短路径。