求联通城市中指定地点到其他地点的最短路径(限3人完成) 设定一个地图，若干城市联通，求指定一城市到其他城市的最短路径。根据数据建立图;能够保存图文件;能够从保存过的图文件中读取图文件;求出指定地点到其他城市的最短路径; 限定C语言

好的，这是一个经典的图论问题，可以使用 Dijkstra 算法来解决。以下是一个简单的实现，限定使用 C 语言。

1. 数据结构定义

我们需要定义一个表示图的数据结构，包括顶点、边以及它们之间的关系。为了方便起见，我们可以使用邻接矩阵来表示图。

// 定义顶点结构体
typedef struct {
    char name[20];  // 顶点名称
} Vertex;

// 定义边结构体
typedef struct {
    int weight;     // 边的权重
} Edge;

// 定义图结构体
typedef struct {
    int num_vertexes;   // 顶点数
    Vertex *vertexes;   // 顶点数组
    Edge **adj_mtx;     // 邻接矩阵
} Graph;

2. 图的初始化

我们可以通过读取文件来初始化图，文件格式如下：

3  // 顶点数
A  // 顶点名称
B
C
0 1 2  // A 到 B 的边权重为 0，A 到 C 的边权重为 1，B 到 C 的边权重为 2
0 0 3
0 0 0

void init_graph(Graph *graph, const char *filename) {
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        perror("Failed to open file");
        exit(1);
    }

    // 读取顶点数
    fscanf(fp, "%d", &graph->num_vertexes);

    // 初始化顶点数组
    graph->vertexes = (Vertex *) malloc(graph->num_vertexes * sizeof(Vertex));
    for (int i = 0; i < graph->num_vertexes; i++) {
        fscanf(fp, "%s", graph->vertexes[i].name);
    }

    // 初始化邻接矩阵
    graph->adj_mtx = (Edge **) malloc(graph->num_vertexes * sizeof(Edge *));
    for (int i = 0; i < graph->num_vertexes; i++) {
        graph->adj_mtx[i] = (Edge *) malloc(graph->num_vertexes * sizeof(Edge));
        for (int j = 0; j < graph->num_vertexes; j++) {
            fscanf(fp, "%d", &graph->adj_mtx[i][j].weight);
        }
    }

    fclose(fp);
}

3. Dijkstra 算法实现

void dijkstra(Graph *graph, int start) {
    // 初始化距离数组和标记数组
    int *dist = (int *) malloc(graph->num_vertexes * sizeof(int));
    int *visited = (int *) calloc(graph->num_vertexes, sizeof(int));
    for (int i = 0; i < graph->num_vertexes; i++) {
        dist[i] = graph->adj_mtx[start][i].weight;
    }

    // 将起点标记为已访问
    visited[start] = 1;

    // 进行 n-1 次迭代
    for (int i = 0; i < graph->num_vertexes - 1; i++) {
        // 找到离起点最近的未访问顶点
        int min_dist = INT_MAX;
        int min_vertex = -1;
        for (int j = 0; j < graph->num_vertexes; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_vertex = j;
            }
        }

        // 标记这个顶点已访问
        visited[min_vertex] = 1;

        // 更新距离数组
        for (int j = 0; j < graph->num_vertexes; j++) {
            if (!visited[j] && graph->adj_mtx[min_vertex][j].weight != 0) {
                int new_dist = dist[min_vertex] + graph->adj_mtx[min_vertex][j].weight;
                if (new_dist < dist[j]) {
                    dist[j] = new_dist;
                }
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < graph->num_vertexes; i++) {
        if (i != start) {
            printf("%s -> %s: %d\n", graph->vertexes[start].name, graph->vertexes[i].name, dist[i]);
        }
    }

    free(dist);
    free(visited);
}

4. 完整代码

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

// 定义顶点结构体
typedef struct {
    char name[20];  // 顶点名称
} Vertex;

// 定义边结构体
typedef struct {
    int weight;     // 边的权重
} Edge;

// 定义图结构体
typedef struct {
    int num_vertexes;   // 顶点数
    Vertex *vertexes;   // 顶点数组
    Edge **adj_mtx;     // 邻接矩阵
} Graph;

void init_graph(Graph *graph, const char *filename) {
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        perror("Failed to open file");
        exit(1);
    }

    // 读取顶点数
    fscanf(fp, "%d", &graph->num_vertexes);

    // 初始化顶点数组
    graph->vertexes = (Vertex *) malloc(graph->num_vertexes * sizeof(Vertex));
    for (int i = 0; i < graph->num_vertexes; i++) {
        fscanf(fp, "%s", graph->vertexes[i].name);
    }

    // 初始化邻接矩阵
    graph->adj_mtx = (Edge **) malloc(graph->num_vertexes * sizeof(Edge *));
    for (int i = 0; i < graph->num_vertexes; i++) {
        graph->adj_mtx[i] = (Edge *) malloc(graph->num_vertexes * sizeof(Edge));
        for (int j = 0; j < graph->num_vertexes; j++) {
            fscanf(fp, "%d", &graph->adj_mtx[i][j].weight);
        }
    }

    fclose(fp);
}

void dijkstra(Graph *graph, int start) {
    // 初始化距离数组和标记数组
    int *dist = (int *) malloc(graph->num_vertexes * sizeof(int));
    int *visited = (int *) calloc(graph->num_vertexes, sizeof(int));
    for (int i = 0; i < graph->num_vertexes; i++) {
        dist[i] = graph->adj_mtx[start][i].weight;
    }

    // 将起点标记为已访问
    visited[start] = 1;

    // 进行 n-1 次迭代
    for (int i = 0; i < graph->num_vertexes - 1; i++) {
        // 找到离起点最近的未访问顶点
        int min_dist = INT_MAX;
        int min_vertex = -1;
        for (int j = 0; j < graph->num_vertexes; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_vertex = j;
            }
        }

        // 标记这个顶点已访问
        visited[min_vertex] = 1;

        // 更新距离数组
        for (int j = 0; j < graph->num_vertexes; j++) {
            if (!visited[j] && graph->adj_mtx[min_vertex][j].weight != 0) {
                int new_dist = dist[min_vertex] + graph->adj_mtx[min_vertex][j].weight;
                if (new_dist < dist[j]) {
                    dist[j] = new_dist;
                }
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < graph->num_vertexes; i++) {
        if (i != start) {
            printf("%s -> %s: %d\n", graph->vertexes[start].name, graph->vertexes[i].name, dist[i]);
        }
    }

    free(dist);
    free(visited);
}

int main() {
    Graph graph;
    init_graph(&graph, "graph.txt");
    dijkstra(&graph, 0);
    return 0;
}