长沙地铁查询系统最优化c语言代码包含查询最短路径

长沙地铁查询系统最优化c语言代码包含查询最短路径需要用到图论算法。以下是一个基于Dijkstra算法的最短路径查询代码示例：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INFINITY 65535 // 无穷大

typedef struct {
  int weight; // 边权值
  char line[20]; // 地铁线路
} EdgeType;

typedef struct {
  char name[20]; // 站点名称
  int num; // 站点编号
} VertexType;

typedef struct {
  int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵，存放边的权值
  int n, e; // n表示顶点数，e表示边数
  VertexType vexs[MAX_VERTEX_NUM]; // 存放顶点信息
} MGraph;

void CreateGraph(MGraph *G) {
  int i, j, k, w;
  char line[20];
  printf("请输入顶点数和边数：\n");
  scanf("%d %d", &G->n, &G->e);
  for (i = 0; i < G->n; i++) {
    printf("请输入第%d个顶点的名称：\n", i + 1);
    scanf("%s", G->vexs[i].name);
    G->vexs[i].num = i + 1;
  }
  for (i = 0; i < G->n; i++) {
    for (j = 0; j < G->n; j++) {
      G->edges[i][j] = INFINITY; // 初始化邻接矩阵
    }
  }
  for (k = 0; k < G->e; k++) {
    printf("请输入边的起始顶点、终止顶点、边权值和地铁线路：\n");
    scanf("%d %d %d %s", &i, &j, &w, line);
    G->edges[i - 1][j - 1] = w;
    G->edges[j - 1][i - 1] = w; // 无向图
    EdgeType *edge = malloc(sizeof(EdgeType));
    edge->weight = w;
    strcpy(edge->line, line);
  }
}

void Dijkstra(MGraph G, int v, int dist[], int path[][MAX_VERTEX_NUM]) {
  int i, j, k, min;
  int *final = malloc(sizeof(int) * G.n);
  for (i = 0; i < G.n; i++) {
    final[i] = 0;
    dist[i] = G.edges[v][i];
    for (j = 0; j < G.n; j++) {
      path[i][j] = 0;
    }
    if (dist[i] < INFINITY) {
      path[i][v] = 1;
      path[i][i] = 1;
    }
  }
  dist[v] = 0;
  final[v] = 1;
  for (i = 1; i < G.n; i++) {
    min = INFINITY;
    for (j = 0; j < G.n; j++) {
      if (!final[j] && dist[j] < min) {
        k = j;
        min = dist[j];
      }
    }
    final[k] = 1;
    for (j = 0; j < G.n; j++) {
      if (!final[j] && min + G.edges[k][j] < dist[j]) {
        dist[j] = min + G.edges[k][j];
        for (int m = 0; m < G.n; m++) {
          path[j][m] = path[k][m];
        }
        path[j][j] = 1;
      }
    }
  }
}

int main() {
  MGraph G;
  int dist[MAX_VERTEX_NUM];
  int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  int start, end;
  CreateGraph(&G);
  printf("请输入起点和终点：\n");
  scanf("%d %d", &start, &end);
  Dijkstra(G, start - 1, dist, path);
  printf("从%s到%s的最短路径长度为：%d\n", G.vexs[start - 1].name, G.vexs[end - 1].name, dist[end - 1]);
  printf("路径为：\n");
  for (int i = 0; i < G.n; i++) {
    if (path[end - 1][i]) {
      printf("%s ", G.vexs[i].name);
    }
  }
  printf("\n");
  return 0;
}

以上代码实现了基于Dijkstra算法的最短路径查询，其中MGraph结构体存储了地铁线路的信息，包括顶点信息和邻接矩阵。Dijkstra函数实现了最短路径的计算，dist数组存储了起点到各个顶点的最短距离，path数组存储了各个顶点的最短路径。最后，根据起点和终点，输出最短路径的长度和路径。