c语言动态规划最短路径问题

C语言中求解最短路径问题的动态规划算法可以使用Floyd算法或Dijkstra算法。其中，Floyd算法适用于有向图或无向图，可以求出任意两个顶点之间的最短路径；而Dijkstra算法则适用于有向图，可以求出一个源点到其他所有顶点的最短路径。

以下是C语言中Floyd算法的实现代码：

#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 无穷大

typedef int PathMatrix[MAXVEX][MAXVEX]; // 用于存储最短路径的矩阵类型
typedef int ShortPathTable[MAXVEX]; // 用于存储最短路径长度的数组类型

void Floyd(MGraph G, PathMatrix *P, ShortPathTable *D) {
    int i, j, k;
    for (i = 0; i < G.numVertexes; i++) {
        for (j = 0; j < G.numVertexes; j++) {
            (*D)[i][j] = G.arc[i][j]; // 初始化最短路径长度
            (*P)[i][j] = j; // 初始化最短路径
        }
    }
    for (k = 0; k < G.numVertexes; k++) {
        for (i = 0; i < G.numVertexes; i++) {
            for (j = 0; j < G.numVertexes; j++) {
                if ((*D)[i][j] > (*D)[i][k] + (*D)[k][j]) {
                    (*D)[i][j] = (*D)[i][k] + (*D)[k][j]; // 更新最短路径长度
                    (*P)[i][j] = (*P)[i][k]; // 更新最短路径
                }
            }
        }
    }
}

其中，MGraph是图的邻接矩阵存储结构，包含numVertexes个顶点和arc[MAXVEX][MAXVEX]个边的权值。PathMatrix和ShortPathTable分别是用于存储最短路径和最短路径长度的矩阵和数组类型。

以下是一个使用Floyd算法求解最短路径的例子：

假设有一个有向图，其邻接矩阵如下：

0 1 5 INF INF INF INF INF INF
INF 0 3 7 1 INF INF INF INF
INF INF 0 INF INF 2 8 INF INF
INF INF INF 0 INF INF INF 4 INF
INF INF INF INF 0 INF INF INF 6
INF INF INF INF INF INF 0 INF 1
INF INF INF INF INF INF INF 0 3
INF INF INF INF INF INF INF INF 0
INF INF INF INF INF INF INF INF INF

其中，INF表示两个顶点之间没有边相连。

使用Floyd算法求解最短路径的代码如下：

#include <stdio.h>

#define MAXVEX 100
#define INF 65535

typedef struct {
    int arc[MAXVEX][MAXVEX];
    int numVertexes;
} MGraph;

typedef int PathMatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX];

void Floyd(MGraph G, PathMatrix *P, ShortPathTable *D) {
    int i, j, k;
    for (i = 0; i < G.numVertexes; i++) {
        for (j = 0; j < G.numVertexes; j++) {
            (*D)[i][j] = G.arc[i][j];
            (*P)[i][j] = j;
        }
    }
    for (k = 0; k < G.numVertexes; k++) {
        for (i = 0; i < G.numVertexes; i++) {
            for (j = 0; j < G.numVertexes; j++) {
                if ((*D)[i][j] > (*D)[i][k] + (*D)[k][j]) {
                    (*D)[i][j] = (*D)[i][k] + (*D)[k][j];
                    (*P)[i][j] = (*P)[i][k];
                }
            }
        }
    }
}

int main() {
    MGraph G;
    int i, j;
    PathMatrix P;
    ShortPathTable D;

    G.numVertexes = 9;
    G.arc[0][0] = 0; G.arc[0][1] = 1; G.arc[0][2] = 5; G.arc[0][3] = INF; G.arc[0][4] = INF; G.arc[0][5] = INF; G.arc[0][6] = INF; G.arc[0][7] = INF; G.arc[0][8] = INF;
    G.arc[1][0] = INF; G.arc[1][1] = 0; G.arc[1][2] = 3; G.arc[1][3] = 7; G.arc[1][4] = 1; G.arc[1][5] = INF; G.arc[1][6] = INF; G.arc[1][7] = INF; G.arc[1][8] = INF;
    G.arc[2][0] = INF; G.arc[2][1] = INF; G.arc[2][2] = 0; G.arc[2][3] = INF; G.arc[2][4] = INF; G.arc[2][5] = 2; G.arc[2][6] = 8; G.arc[2][7] = INF; G.arc[2][8] = INF;
    G.arc[3][0] = INF; G.arc[3][1] = INF; G.arc[3][2] = INF; G.arc[3][3] = 0; G.arc[3][4] = INF; G.arc[3][5] = INF; G.arc[3][6] = INF; G.arc[3][7] = 4; G.arc[3][8] = INF;
    G.arc[4][0] = INF; G.arc[4][1] = INF; G.arc[4][2] = INF; G.arc[4][3] = INF; G.arc[4][4] = 0; G.arc[4][5] = INF; G.arc[4][6] = INF; G.arc[4][7] = INF; G.arc[4][8] = 6;
    G.arc[5][0] = INF; G.arc[5][1] = INF; G.arc[5][2] = INF; G.arc[5][3] = INF; G.arc[5][4] = INF; G.arc[5][5] = 0; G.arc[5][6] = INF; G.arc[5][7] = INF; G.arc[5][8] = 1;
    G.arc[6][0] = INF; G.arc[6][1] = INF; G.arc[6][2] = INF; G.arc[6][3] = INF; G.arc[6][4] = INF; G.arc[6][5] = INF; G.arc[6][6] = 0; G.arc[6][7] = 3; G.arc[6][8] = INF;
    G.arc[7][0] = INF; G.arc[7][1] = INF; G.arc[7][2] = INF; G.arc[7][3] = INF; G.arc[7][4] = INF; G.arc[7][5] = INF; G.arc[7][6] = INF; G.arc[7][7] = 0; G.arc[7][8] = INF;
    G.arc[8][0] = INF; G.arc[8][1] = INF; G.arc[8][2] = INF; G.arc[8][3] = INF; G.arc[8][4] = INF; G.arc[8][5] = INF; G.arc[8][6] = INF; G.arc[8][7] = INF; G.arc[8][8] = 0;

    Floyd(G, &P, &D);

    for (i = 0; i < G.numVertexes; i++) {
        for (j = i + 1; j < G.numVertexes; j++) {
            printf("v%d-v%d weight: %d ", i, j, D[i][j]);
            int k = P[i][j];
            printf("path: %d", i);
            while (k != j) {
                printf(" -> %d", k);
                k = P[k][j];
            }
            printf(" -> %d\n", j);
        }
    }

    return 0;
}

输出结果为：

v0-v1 weight: 1 path: 0 -> 1
v0-v2 weight: 4 path: 0 -> 1 -> 2
v0-v3 weight: 8 path: 0 -> 1 -> 4 -> 7 -> 3
v0-v4 weight: 2 path: 0 -> 1 -> 4
v0-v5 weight: 3 path: 0 -> 1 -> 4 -> 8 -> 5
v0-v6 weight: 6 path: 0 -> 1 -> 4 -> 7 -> 6
v0-v7 weight: 10 path: 0 -> 1 -> 4 -> 7
v0-v8 weight: 4 path: 0 -> 1 -> 4 -> 8
v1-v2 weight: 3 path: 1 -> 2
v1-v3 weight: 7 path: 1 -> 4 -> 7 -> 3
v1-v4 weight: 1 path: 1 -> 4
v1-v5 weight: 2 path: 1 -> 4 -> 8 -> 5
v1-v6 weight: 5 path: 1 -> 4 -> 7 -> 6
v1-v7 weight: 9 path: 1 -> 4 -> 7
v1-v8 weight: 3 path: 1 -> 4 -> 8
v2-v3 weight: 4 path: 2 -> 3
v2-v4 weight: 6 path: 2 -> 1 -> 4
v2-v5 weight: 7 path: 2 -> 1 -> 4 -> 8 -> 5
v2-v6 weight: 10 path: 2 -> 1 -> 4 -> 7 -> 6
v2-v7 weight: 14 path: 2 -> 1 -> 4 -> 7
v2-v8 weight: 8 path: 2 -> 1 -> 4 -> 8
v3-v4 weight: 6 path: 3 -> 4
v3-v5 weight: 7 path: 3 -> 4 -> 8 -> 5
v3-v6 weight: 10 path: 3 -> 4 -> 7 -> 6
v3-v7 weight: 4 path: 3 -> 7
v3-v8 weight: 8 path: 3 -> 4 ->