c语言邻接表计算最短距离

根据提供的引用内容，以下是使用C语言邻接表计算最短距离的示例代码：

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

// 定义图的最大顶点数
#define MAX_VERTICES 100

// 定义邻接表中的边结构
typedef struct Edge {
    int dest;   // 目标顶点
    int weight; // 边的权值
    struct Edge* next; // 指向下一条边的指针
} Edge;

// 定义邻接表中的顶点结构
typedef struct Vertex {
    Edge* head; // 指向第一条边的指针
} Vertex;

// 定义图结构
typedef struct Graph {
    int numVertices; // 顶点数
    Vertex* array;   // 邻接表数组
} Graph;

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->array = (Vertex*)malloc(numVertices * sizeof(Vertex));

    // 初始化邻接表中的顶点
    for (int i = 0; i < numVertices; i++) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest, int weight) {
    // 创建新的边节点
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->dest = dest;
    newEdge->weight = weight;
    newEdge->next = graph->array[src].head;

    // 将新的边节点插入到邻接表中
    graph->array[src].head = newEdge;
}

// 计算最短距离
void shortestPath(Graph* graph, int startVertex) {
    int numVertices = graph->numVertices;
    int* dist = (int*)malloc(numVertices * sizeof(int));
    int* visited = (int*)malloc(numVertices * sizeof(int));

    // 初始化距离数组和访问数组
    for (int i = 0; i < numVertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    // 设置起始顶点的距离为0
    dist[startVertex] = 0;

    // 计算最短距离
    for (int count = 0; count < numVertices - 1; count++) {
        int minDist = INT_MAX;
        int minIndex = -1;

        // 选择距离最小的顶点
        for (int v = 0; v < numVertices; v++) {
            if (visited[v] == 0 && dist[v] <= minDist) {
                minDist = dist[v];
                minIndex = v;
            }
        }

        // 标记选中的顶点为已访问
        visited[minIndex] = 1;

        // 更新相邻顶点的最短距离
        Edge* edge = graph->array[minIndex].head;
        while (edge != NULL) {
            int dest = edge->dest;
            int weight = edge->weight;

            if (visited[dest] == 0 && dist[minIndex] != INT_MAX && dist[minIndex] + weight < dist[dest]) {
                dist[dest] = dist[minIndex] + weight;
            }

            edge = edge->next;
        }
    }

    // 输出最短距离
    printf("最短距离：\n");
    for (int i = 0; i < numVertices; i++) {
        printf("从顶点 %d 到顶点 %d 的最短距离为 %d\n", startVertex, i, dist[i]);
    }

    // 释放内存
    free(dist);
    free(visited);
}

int main() {
    int numVertices = 5;
    Graph* graph = createGraph(numVertices);

    // 添加边到图中
    addEdge(graph, 0, 1, 10);
    addEdge(graph, 0, 4, 5);
    addEdge(graph, 1, 2, 1);
    addEdge(graph, 1, 4, 2);
    addEdge(graph, 2, 3, 4);
    addEdge(graph, 3, 2, 6);
    addEdge(graph, 3, 0, 7);
    addEdge(graph, 4, 1, 3);
    addEdge(graph, 4, 2, 9);
    addEdge(graph, 4, 3, 2);

    int startVertex = 0;
    shortestPath(graph, startVertex);

    return 0;
}