c语言利用动态规划实现迪杰斯特拉算法

迪杰斯特拉算法是一种用于求解单源最短路径问题的算法，其基本思想是以起点为中心，逐步扩展出各个顶点的最短路径。动态规划是一种解决问题的思想，它将原问题分解成若干子问题，通过求解子问题的最优解，来求解原问题的最优解。

下面是利用动态规划实现迪杰斯特拉算法的C语言代码：

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

#define MAX_VERTICES 1000

// 定义图的结构体
typedef struct {
    int weight[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵
    int n; // 图中顶点的个数
} Graph;

// 定义最短路径结构体
typedef struct {
    int distance[MAX_VERTICES]; // 起点到各个顶点的最短距离
    int visited[MAX_VERTICES]; // 是否已访问过
    int parent[MAX_VERTICES]; // 记录最短路径上每个顶点的前一个顶点
} ShortestPath;

// 初始化图
void initGraph(Graph* g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->weight[i][j] = INT_MAX;
        }
    }
}

// 添加边
void addEdge(Graph* g, int u, int v, int w) {
    g->weight[u][v] = w;
}

// 执行迪杰斯特拉算法
void dijkstra(Graph* g, int s, ShortestPath* sp) {
    // 初始化最短路径结构体
    for (int i = 0; i < g->n; i++) {
        sp->distance[i] = INT_MAX;
        sp->visited[i] = 0;
        sp->parent[i] = -1;
    }
    sp->distance[s] = 0;

    // 逐步扩展出各个顶点的最短路径
    for (int i = 0; i < g->n; i++) {
        int u = -1; // 找到距离起点最近且未访问过的顶点
        for (int j = 0; j < g->n; j++) {
            if (!sp->visited[j] && (u == -1 || sp->distance[j] < sp->distance[u])) {
                u = j;
            }
        }
        if (sp->distance[u] == INT_MAX) { // 如果找不到未访问过的顶点，说明剩下的顶点和起点不连通
            break;
        }
        sp->visited[u] = 1; // 标记该顶点已访问过
        for (int v = 0; v < g->n; v++) { // 更新与该顶点相邻的顶点的最短距离
            if (g->weight[u][v] != INT_MAX) {
                int newDistance = sp->distance[u] + g->weight[u][v];
                if (newDistance < sp->distance[v]) {
                    sp->distance[v] = newDistance;
                    sp->parent[v] = u;
                }
            }
        }
    }
}

// 输出最短路径
void printShortestPath(ShortestPath* sp, int s, int d) {
    if (d == s) {
        printf("%d", s);
        return;
    }
    if (sp->parent[d] == -1) {
        printf("No path.");
        return;
    }
    printShortestPath(sp, s, sp->parent[d]);
    printf(" -> %d", d);
}

int main() {
    Graph g;
    initGraph(&g, 5);
    addEdge(&g, 0, 1, 10);
    addEdge(&g, 0, 3, 5);
    addEdge(&g, 1, 2, 1);
    addEdge(&g, 1, 3, 2);
    addEdge(&g, 2, 4, 4);
    addEdge(&g, 3, 1, 3);
    addEdge(&g, 3, 2, 9);
    addEdge(&g, 3, 4, 2);
    addEdge(&g, 4, 0, 7);
    addEdge(&g, 4, 2, 6);

    ShortestPath sp;
    dijkstra(&g, 0, &sp);
    for (int i = 0; i < g.n; i++) {
        printf("Shortest path to %d: %d\n", i, sp.distance[i]);
        printf("Path: ");
        printShortestPath(&sp, 0, i);
        printf("\n");
    }

    return 0;
}

在上面的代码中，我们定义了一个 `Graph` 结构体来表示图，其中包含图的邻接矩阵和顶点个数。我们使用 `initGraph` 函数来初始化图，使用 `addEdge` 函数来添加边。我们还定义了一个 `ShortestPath` 结构体来表示最短路径，其中包含起点到各个顶点的最短距离、是否已访问过以及最短路径上每个顶点的前一个顶点。

在 `dijkstra` 函数中，我们首先初始化最短路径结构体，然后逐步扩展出各个顶点的最短路径。我们使用一个 `visited` 数组来记录哪些顶点已经访问过了，使用一个 `parent` 数组来记录最短路径上每个顶点的前一个顶点。在每次扩展顶点时，我们找到距离起点最近且未访问过的顶点，并标记该顶点已访问过。然后，更新与该顶点相邻的顶点的最短距离和前一个顶点。

最后，在 `main` 函数中，我们创建一个图，并执行迪杰斯特拉算法。对于每个顶点，我们输出起点到该顶点的最短距离和最短路径。