用c【问题描述】最短路径问题实际上是带权有向图（网）的一种应用，用Dijkstra算法求两个顶点间的最短路径。备注：输入的有向网信息中0表示不存在顶点到自身的弧，32767表示两个顶点之间不存在弧。 【输入形式】带权有向图（网）的顶点数及，有向图（网）的信息，出发顶点。 【输出形式】输出出发顶点到有向图（网）其余顶点间的最短路径长度及其路径。

以下是用C语言实现Dijkstra算法求解带权有向图最短路径问题的示例代码：

#include <stdio.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INFINITY 32767 // 无穷大

// 有向图（网）的邻接矩阵表示
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点信息
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 弧信息
    int vexnum, arcnum; // 顶点数和弧数
} MGraph;

// Dijkstra算法求最短路径
void Dijkstra(MGraph G, int v0, int dist[], int path[]) {
    int visited[MAX_VERTEX_NUM] = {0}; // 是否已访问
    visited[v0] = 1;
    for (int i = 0; i < G.vexnum; i++) {
        dist[i] = G.arcs[v0][i]; // 初始化dist数组
        if (G.arcs[v0][i] < INFINITY) {
            path[i] = v0; // 初始化path数组
        }
    }
    for (int i = 1; i < G.vexnum; i++) { // 循环n-1次
        int min = INFINITY;
        int u = v0;
        for (int j = 0; j < G.vexnum; j++) { // 找到未访问的dist最小的顶点
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        visited[u] = 1;
        for (int j = 0; j < G.vexnum; j++) { // 更新dist和path数组
            if (!visited[j] && G.arcs[u][j] < INFINITY && dist[u] + G.arcs[u][j] < dist[j]) {
                dist[j] = dist[u] + G.arcs[u][j];
                path[j] = u;
            }
        }
    }
}

// 输出最短路径
void PrintPath(MGraph G, int v0, int dist[], int path[]) {
    for (int i = 0; i < G.vexnum; i++) {
        if (i != v0) {
            printf("%d到%d的最短路径长度为%d，路径为", v0, i, dist[i]);
            int j = i;
            while (j != v0) { // 逆序输出路径
                printf("%d<-", j);
                j = path[j];
            }
            printf("%d\n", j);
        }
    }
}

int main() {
    MGraph G;
    int v0;
    printf("请输入顶点数和弧数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入顶点信息：");
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%d", &G.vertex[i]);
    }
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = INFINITY;
        }
    }
    printf("请输入弧信息（用32767表示不存在弧）：\n");
    for (int k = 0; k < G.arcnum; k++) {
        int i, j, w;
        scanf("%d%d%d", &i, &j, &w);
        G.arcs[i][j] = w;
    }
    printf("请输入出发顶点：");
    scanf("%d", &v0);
    int dist[MAX_VERTEX_NUM], path[MAX_VERTEX_NUM];
    Dijkstra(G, v0, dist, path);
    PrintPath(G, v0, dist, path);
    return 0;
}

输入格式示例：

请输入顶点数和弧数：5 7
请输入顶点信息：0 1 2 3 4
请输入弧信息（用32767表示不存在弧）：
0 1 10
0 4 30
1 2 50
1 4 40
2 3 30
3 2 20
3 0 60
请输入出发顶点：0

输出格式示例：

0到1的最短路径长度为10，路径为0<-1
0到2的最短路径长度为60，路径为0<-1<-2
0到3的最短路径长度为50，路径为0<-4<-1<-2<-3
0到4的最短路径长度为30，路径为0<-4