迪杰斯特拉算法C语言

迪杰斯特拉算法是一种用于解决带权有向图中单源最短路径问题的算法。它的基本思想是从起点开始，每次选择当前最短路径的顶点，并更新与该顶点相邻的顶点的距离。具体实现可以使用优先队列来维护当前最短路径的顶点。

以下是迪杰斯特拉算法的C语言实现：

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

#define MAX_VERTICES 1000

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

typedef struct {
    Edge* edges[MAX_VERTICES];
    int size[MAX_VERTICES];
    int capacity[MAX_VERTICES];
} Graph;

Graph* createGraph(int n) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    for (int i = 0; i < n; i++) {
        graph->size[i] = 0;
        graph->capacity[i] = 1;
        graph->edges[i] = (Edge*)malloc(sizeof(Edge) * graph->capacity[i]);
    }
    return graph;
}

void addEdge(Graph* graph, int u, int v, int weight) {
    if (graph->size[u] == graph->capacity[u]) {
        graph->capacity[u] *= 2;
        graph->edges[u] = (Edge*)realloc(graph->edges[u], sizeof(Edge) * graph->capacity[u]);
    }
    graph->edges[u][graph->size[u]].v = v;
    graph->edges[u][graph->size[u]].weight = weight;
    graph->size[u]++;
}

void dijkstra(Graph* graph, int start, int* dist, int* prev) {
    int visited[MAX_VERTICES] = {0};
    for (int i = 0; i < MAX_VERTICES; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
    }
    dist[start] = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        int u = -1;
        for (int j = 0; j < MAX_VERTICES; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        if (dist[u] == INT_MAX) {
            break;
        }
        visited[u] = 1;
        for (int j = 0; j < graph->size[u]; j++) {
            int v = graph->edges[u][j].v;
            int weight = graph->edges[u][j].weight;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
            }
        }
    }
}

int main() {
    Graph* graph = createGraph(5);
    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 dist[MAX_VERTICES];
    int prev[MAX_VERTICES];
    dijkstra(graph, 0, dist, prev);

    for (int i = 0; i < 5; i++) {
        printf("Shortest distance from vertex 0 to vertex %d is %d\n", i, dist[i]);
    }

    return 0;
}