C语言实现迪杰斯特拉算法求最短路径

以下是使用迪杰斯特拉算法设计的一个C语言代码，用于求解给定带权有向图G和源点v0到其余各点的最短路径。

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

#define MAX_SIZE 100
#define INF 9999

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    int vertex;
    int distance;
} Vertex;

typedef struct {
    Edge* edges[MAX_SIZE];
    int edgeCount;
    Vertex* vertices[MAX_SIZE];
    int vertexCount;
} Graph;

Graph* createGraph() {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->edgeCount = 0;
    graph->vertexCount = 0;
    return graph;
}

void addVertex(Graph* graph, int vertex) {
    Vertex* v = (Vertex*)malloc(sizeof(Vertex));
    v->vertex = vertex;
    v->distance = INF;
    graph->vertices[graph->vertexCount++] = v;
}

void addEdge(Graph* graph, int start, int end, int weight) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->vertex = end;
    edge->weight = weight;
    graph->edges[graph->edgeCount++] = edge;
}

void dijkstra(Graph* graph, int start) {
    Vertex* source = graph->vertices[start];
    source->distance = 0;
    
    bool visited[MAX_SIZE] = {false};
    
    for (int count = 0; count < graph->vertexCount - 1; count++) {
        int minDistance = INF;
        int minIndex = -1;
        
        for (int i = 0; i < graph->vertexCount; i++) {
            if (!visited[i] && graph->vertices[i]->distance < minDistance) {
                minDistance = graph->vertices[i]->distance;
                minIndex = i;
            }
        }
        
        visited[minIndex] = true;
        
        for (int i = 0; i < graph->edgeCount; i++) {
            Edge* edge = graph->edges[i];
            if (edge->vertex == minIndex && !visited[edge->vertex]) {
                int newDistance = source->distance + edge->weight;
                if (newDistance < graph->vertices[edge->vertex]->distance) {
                    graph->vertices[edge->vertex]->distance = newDistance;
                }
            }
        }
    }
}

int main() {
    Graph* graph = createGraph();
    
    // 添加顶点
    addVertex(graph, 0);
    addVertex(graph, 1);
    addVertex(graph, 2);
    addVertex(graph, 3);
    addVertex(graph, 4);
    
    // 添加边
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 2, 2);
    addEdge(graph, 1, 2, 3);
    addEdge(graph, 1, 3, 2);
    addEdge(graph, 1, 4, 3);
    addEdge(graph, 3, 2, 5);
    addEdge(graph, 3, 1, 1);
    addEdge(graph, 4, 3, 1);
    
    // 使用迪杰斯特拉算法求最短路径
    dijkstra(graph, 0);
    
    // 打印结果
    for (int i = 0; i < graph->vertexCount; i++) {
        printf("最短路径从顶点 0 到顶点 %d 的距离为：%d\n", graph->vertices[i]->vertex, graph->vertices[i]->distance);
    }
    
    return 0;
}

在这个代码中，Graph 结构表示有向图，包含了顶点数组 vertices 和边数组 edges。Vertex 结构表示顶点，包含了顶点的索引 vertex 和从源点到该顶点的最短距离 distance。Edge 结构表示边，包含了边的终点 vertex 和边的权重 weight。

首先，我们创建图并添加顶点和边。然后使用迪杰斯特拉算法计算从源点到各个顶点的最短路径。最后，打印结果，显示从源点到每个顶点的最短距离。

注意，上述代码中的图使用了邻接表的方式来表示。如果需要使用邻接矩阵来表示图，可以做相应的修改。