使用c语言实现迪杰斯特拉算法，要求得到最短路径以及最短路径长度

迪杰斯特拉算法是一种解决单源最短路径问题的贪心算法，其基本思想是维护一个距离起点距离最短的顶点集合，逐步扩充这个集合，直到到达终点或者无法再扩充为止。以下是使用C语言实现迪杰斯特拉算法的代码：

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

// 定义图的最大大小
#define MAX_SIZE 100

// 定义一个结构体表示图中的边
typedef struct {
    int to;
    int weight;
} Edge;

// 定义一个结构体表示图中的顶点
typedef struct {
    int id;
    int dist;
    int visited;
    Edge edges[MAX_SIZE];
    int num_edges;
} Vertex;

// 定义一个结构体表示整个图
typedef struct {
    Vertex vertices[MAX_SIZE];
    int num_vertices;
} Graph;

// 初始化图
void init_graph(Graph *g) {
    g->num_vertices = 0;
}

// 添加顶点
void add_vertex(Graph *g, int id) {
    g->vertices[g->num_vertices].id = id;
    g->vertices[g->num_vertices].dist = INT_MAX;
    g->vertices[g->num_vertices].visited = 0;
    g->vertices[g->num_vertices].num_edges = 0;
    g->num_vertices++;
}

// 添加边
void add_edge(Graph *g, int from, int to, int weight) {
    Edge new_edge = {to, weight};
    g->vertices[from].edges[g->vertices[from].num_edges] = new_edge;
    g->vertices[from].num_edges++;
}

// 获取未访问顶点中距离起点最近的顶点
Vertex *get_closest_unvisited_vertex(Graph *g) {
    int min_dist = INT_MAX;
    Vertex *closest_vertex = NULL;
    for (int i = 0; i < g->num_vertices; i++) {
        if (!g->vertices[i].visited && g->vertices[i].dist < min_dist) {
            min_dist = g->vertices[i].dist;
            closest_vertex = &g->vertices[i];
        }
    }
    return closest_vertex;
}

// 迪杰斯特拉算法
void dijkstra(Graph *g, int start, int end) {
    // 初始化起点
    g->vertices[start].dist = 0;
    Vertex *current_vertex = &g->vertices[start];
    // 逐步扩充最短路径集合
    while (current_vertex != NULL) {
        // 标记当前顶点为已访问
        current_vertex->visited = 1;
        // 更新与当前顶点相邻的顶点的距离
        for (int i = 0; i < current_vertex->num_edges; i++) {
            Edge *edge = &current_vertex->edges[i];
            Vertex *adjacent_vertex = &g->vertices[edge->to];
            if (!adjacent_vertex->visited) {
                int new_dist = current_vertex->dist + edge->weight;
                if (new_dist < adjacent_vertex->dist) {
                    adjacent_vertex->dist = new_dist;
                }
            }
        }
        // 获取下一个未访问顶点中距离起点最近的顶点
        current_vertex = get_closest_unvisited_vertex(g);
    }
    // 输出最短路径长度
    printf("The shortest path from %d to %d has length %d\n", start, end, g->vertices[end].dist);
    // 输出最短路径
    printf("The shortest path is: ");
    current_vertex = &g->vertices[end];
    while (current_vertex != NULL) {
        printf("%d ", current_vertex->id);
        if (current_vertex->id == start) {
            break;
        }
        for (int i = 0; i < current_vertex->num_edges; i++) {
            Edge *edge = &current_vertex->edges[i];
            Vertex *adjacent_vertex = &g->vertices[edge->to];
            if (adjacent_vertex->dist == current_vertex->dist - edge->weight) {
                current_vertex = adjacent_vertex;
                break;
            }
        }
    }
    printf("\n");
}

int main() {
    Graph g;
    init_graph(&g);

    // 添加顶点
    add_vertex(&g, 0);
    add_vertex(&g, 1);
    add_vertex(&g, 2);
    add_vertex(&g, 3);
    add_vertex(&g, 4);
    add_vertex(&g, 5);

    // 添加边
    add_edge(&g, 0, 1, 2);
    add_edge(&g, 0, 3, 1);
    add_edge(&g, 1, 2, 3);
    add_edge(&g, 1, 3, 2);
    add_edge(&g, 1, 4, 1);
    add_edge(&g, 2, 5, 2);
    add_edge(&g, 3, 4, 4);
    add_edge(&g, 4, 5, 3);

    // 执行迪杰斯特拉算法
    dijkstra(&g, 0, 5);

    return 0;
}

上述代码实现了一个简单的图，其中顶点0到顶点5的最短路径为0->1->4->5，路径长度为6。在实现中，我们使用了三个结构体来表示图中的顶点、边以及整个图。`init_graph()`函数用于初始化图，`add_vertex()`函数用于添加顶点，`add_edge()`函数用于添加边。`dijkstra()`函数用于执行迪杰斯特拉算法，并输出最短路径以及最短路径长度。其中，`get_closest_unvisited_vertex()`函数用于获取未访问顶点中距离起点最近的顶点。