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(' '); }

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; } 输入什么运行内容：可以按照以下步骤运行程序：

打开一个C语言编译器，如Dev-C++、Visual Studio等。
将上述代码复制到编译器中，并保存为一个C文件（如graph.c）。
编译并运行程序。
在程序提示输入起点和终点时，按照提示输入两个景点名称，如'南门'和'图书馆'。
程序会输出最短路径，如'最短路径为：南门->东门->北门->图书馆'。