给定任意一张带权值的有向连通图，请采用Dijkstra算法输出从给定结点到其余结点的最短路径以及路径长度，给出c语言代码

以下是基于邻接矩阵的Dijkstra算法的C语言代码：

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100
#define INF 999999

int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
bool visited[MAX_VERTICES];
int parent[MAX_VERTICES];

int minDistance(int n) {
    int min = INF, minIndex;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] <= min) {
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

void dijkstra(int n, int start) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;
    parent[start] = -1;
    for (int i = 0; i < n - 1; i++) {
        int u = minDistance(n);
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
        }
    }
}

void printPath(int end) {
    if (parent[end] == -1) {
        printf("%d ", end);
        return;
    }
    printPath(parent[end]);
    printf("%d ", end);
}

int main() {
    int n, start;
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("Enter the adjacency matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    printf("Enter the starting vertex: ");
    scanf("%d", &start);
    dijkstra(n, start);
    printf("Shortest distances from vertex %d:\n", start);
    for (int i = 0; i < n; i++) {
        if (i != start) {
            printf("Vertex %d: %d, Path: ", i, dist[i]);
            printPath(i);
            printf("\n");
        }
    }
    return 0;
}

输入格式为：

Enter the number of vertices: 5
Enter the adjacency matrix:
0 10 3 0 0
0 0 1 2 0
0 4 0 8 2
0 0 0 0 7
0 0 0 9 0
Enter the starting vertex: 0

输出格式为：

Shortest distances from vertex 0:
Vertex 1: 10, Path: 1 
Vertex 2: 3, Path: 2 0 
Vertex 3: 12, Path: 2 0 3 
Vertex 4: 14, Path: 2 0 3 4