【问题描述】最短路径问题实际上是带权有向图（网）的一种应用，用Dijkstra算法求两个顶点间的最短路径。备注：输入的有向网信息中0表示不存在顶点到自身的弧，32767表示两个顶点之间不存在弧。 【输入形式】带权有向图（网）的顶点数及，有向图（网）的信息，出发顶点。 【输出形式】输出出发顶点到有向图（网）其余顶点间的最短路径长度及其路径。 【样例输入】 输入顶点数： 7 输入有向网的信息： 0 4 6 6 32767 32767 32767 32767 0 1 32767 7 32767 32767 32767 32767 0 32767 6 4 32767 32767 32767 2 0 32767 5 32767 32767 32767 32767 32767 0 32767 6 32767 32767 32767 32767 1 0 8 32767 32767 32767 32767 32767 32767 0 输入出发顶点： 0 【样例输出】 从0顶点出发的最短路径如下: 从顶点0到顶点1的路径长度为:4 路径为:0,1 从顶点0到顶点2的路径长度为:5 路径为:0,1,2 从顶点0到顶点3的路径长度为:6 路径为:0,3 从顶点0到顶点4的路径长度为:10 路径为:0,1,2,5,4 从顶点0到顶点5的路径长度为:9 路径为:0,1,2,5 从顶点0到顶点6的路径长度为:16 路径为:0,1,2,5,4,6 使用c语言完成

以下是C语言实现Dijkstra算法解决最短路径问题的代码，注释中有详细解释：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20    // 图的最大顶点数
#define INFINITY 32767       // 定义无穷大

typedef struct {
    int adj;                  // 记录两个顶点间边的权值
    char info[20];            // 存储边的相关信息（可选）
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    int vexs[MAX_VERTEX_NUM];   // 存储顶点信息
    AdjMatrix arcs;             // 存储边信息
    int vexnum, arcnum;         // 存储图的顶点数和边数
} MGraph;

// 构造有向网
void CreateMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入有向网的顶点数和边数：\n");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入有向网的顶点信息：\n");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = INFINITY;   // 初始化所有边的权值为无穷大
        }
    }
    printf("请输入有向网的边信息（起点 终点 权值）：\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d %d", &i, &j, &w);
        G->arcs[i][j].adj = w;
    }
}

// Dijkstra算法求有向网中某一顶点到其他所有顶点的最短路径
void ShortestPath_DIJ(MGraph G, int v, int dist[], int path[][MAX_VERTEX_NUM]) {
    int final[MAX_VERTEX_NUM], i, j, k, min;
    // 初始化
    for (i = 0; i < G.vexnum; i++) {
        final[i] = 0;   // 表示顶点i是否已经求得最短路径，0表示未求得，1表示已求得
        dist[i] = G.arcs[v][i].adj;   // 存储v到i的最短距离
        for (j = 0; j < G.vexnum; j++) {
            path[i][j] = 0;   // 存储v到i最短路径上的顶点序列
        }
        if (dist[i] < INFINITY) {
            path[i][v] = 1;
            path[i][i] = 1;   // 如果v和i之间有边，则设置path[i][v]和path[i][i]为1
        }
    }
    dist[v] = 0;
    final[v] = 1;
    // 开始循环，每次求得一个顶点到v的最短路径
    for (i = 1; i < G.vexnum; i++) {
        min = INFINITY;
        // 找到离v最近的顶点k
        for (j = 0; j < G.vexnum; j++) {
            if (!final[j] && dist[j] < min) {
                k = j;
                min = dist[j];
            }
        }
        final[k] = 1;   // 标记顶点k已经求得最短路径
        // 更新dist和path数组
        for (j = 0; j < G.vexnum; j++) {
            if (!final[j] && min+G.arcs[k][j].adj < dist[j]) {
                dist[j] = min+G.arcs[k][j].adj;
                // 将k加入v到j的最短路径中
                for (int m = 0; m < G.vexnum; m++) {
                    path[j][m] = path[k][m];
                }
                path[j][j] = 1;
            }
        }
    }
}

// 输出最短路径
void PrintPath(int dist[], int path[][MAX_VERTEX_NUM], int v) {
    int i, j, k;
    for (i = 0; i < v; i++) {
        printf("从顶点%d到顶点%d的路径长度为：%d\t", v, i, dist[i]);
        printf("路径为：%d", v);
        j = i;
        while (path[i][j] != 1) {
            for (k = 0; k < v; k++) {
                if (path[i][k] == 1 && G.arcs[k][j].adj < INFINITY) {
                    printf("->%d", k);
                    j = k;
                    break;
                }
            }
        }
        printf("->%d\n", i);
    }
}

int main() {
    MGraph G;
    int dist[MAX_VERTEX_NUM];   // 存储最短路径长度
    int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   // 存储最短路径上的顶点序列
    printf("构造有向网：\n");
    CreateMGraph(&G);
    printf("请输入出发顶点：\n");
    int v;
    scanf("%d", &v);
    ShortestPath_DIJ(G, v, dist, path);
    printf("从%d顶点出发的最短路径如下：\n", v);
    PrintPath(dist, path, G.vexnum);
    return 0;
}