dijkstra算法c++代码实现。输入：第一行，三个整数，$vn,en,s $，用空格分开，分别表示图G中：顶点数目（顶点编号从0开始），弧的数量（无向图每对顶点之间有两条弧），Dijkstra算法指定的起点。其中：1≤ vn ≤ 1000， 1≤ en ≤ vn×（vn-1）。注意：案例中提供的弧可以有重复的，图应该按照最后一次的弧的设置为准，即SetEdge的语义当存在该弧时，设置权值。 之后会有en行，每行表示一对顶点之间的一条弧，形式为："<"+from+", "+to+", "+weight+">"，其中from为弧的起点，to为弧的终点，weight为弧上权值（每对顶点之间的不同的弧上的权值可以不同）输出：共vn行，第i行表示编号为i的顶点（第i个顶点，i从0开始）到起点s的最短路径长度len，以及该最短路径中的前驱顶点p（起始顶点s的前驱设为自身顶点编号s）。示例：输入10 32 0 <2, 1, 2> <1, 2, 2> <5, 8, 52> <8, 5, 52> <1, 7, 141> <7, 1, 141> <0, 8, 185> <8, 0, 185> <3, 8, 43> <8, 3, 43> <7, 8, 136> <8, 7, 136> <1, 2, 122> <2, 1, 122> <6, 8, 150> <8, 6, 150> <2, 1, 6> <1, 2, 6> <6, 3, 16> <3, 6, 16> <7, 9, 34> <9, 7, 34> <3, 1, 10> <1, 3, 10> <8, 9, 193> <9, 8, 193> <7, 8, 49> <8, 7, 49> <0, 1, 198> <1, 0, 198> <0, 5, 179> <5, 0, 179>输出：<0, 0, 0> <1, 198, 0> <2, 204, 1> <3, 208, 1> <4, INF, 0> <5, 179, 0> <6, 224, 3> <7, 234, 8> <8, 185, 0> <9, 268, 7>

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

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

#define MAX_VERTICES 1000
#define INF INT_MAX

typedef struct {
    int vertex;  // 边的终点
    int weight;  // 边的权重
    struct EdgeNode *next;
} EdgeNode;  // 边的节点

typedef struct {
    EdgeNode *first;  // 第一条边
} VertexNode;  // 顶点的节点

int vn, en, s;  // 顶点数目，弧的数量，起点
VertexNode graph[MAX_VERTICES];  // 图的邻接表

// 添加一条边
void SetEdge(int from, int to, int weight) {
    EdgeNode *p = graph[from].first;

    // 如果该顶点没有边，则新建一条边
    if (p == NULL) {
        p = (EdgeNode*)malloc(sizeof(EdgeNode));
        p->vertex = to;
        p->weight = weight;
        p->next = NULL;
        graph[from].first = p;
        return;
    }

    // 查找是否已经存在该边
    while (p->next != NULL) {
        if (p->vertex == to) {
            p->weight = weight;  // 如果已经存在该边，则更新权值
            return;
        }
        p = p->next;
    }

    // 如果不存在该边，则新建一条边
    if (p->vertex != to) {
        EdgeNode *q = (EdgeNode*)malloc(sizeof(EdgeNode));
        q->vertex = to;
        q->weight = weight;
        q->next = NULL;
        p->next = q;
    } else {
        p->weight = weight;  // 如果已经存在该边，则更新权值
    }
}

// Dijkstra算法
void Dijkstra(int s, int *len, int *p) {
    int i, j, v, min;
    int visited[MAX_VERTICES];  // 标记每个顶点是否已被访问
    EdgeNode *p_node;

    // 初始化距离和前驱
    for (i = 0; i < vn; i++) {
        visited[i] = 0;
        len[i] = INF;
        p[i] = -1;
    }
    len[s] = 0;

    // 进行vn次循环，每次找到一个未被访问的距离最小的顶点v
    for (i = 0; i < vn; i++) {
        v = -1;
        min = INF;
        for (j = 0; j < vn; j++) {
            if (!visited[j] && len[j] < min) {
                v = j;
                min = len[j];
            }
        }

        // 如果未找到未被访问的顶点，则退出循环
        if (v == -1) {
            break;
        }

        // 标记该顶点为已访问
        visited[v] = 1;

        // 对v的每一条边进行松弛操作
        p_node = graph[v].first;
        while (p_node != NULL) {
            if (!visited[p_node->vertex] && len[v] + p_node->weight < len[p_node->vertex]) {
                len[p_node->vertex] = len[v] + p_node->weight;
                p[p_node->vertex] = v;
            }
            p_node = p_node->next;
        }
    }
}

int main() {
    int i, from, to, weight;
    int len[MAX_VERTICES], p[MAX_VERTICES];

    // 读入顶点数目，弧的数量和起点
    scanf("%d%d%d", &vn, &en, &s);

    // 读入每一条边并添加到邻接表中
    for (i = 0; i < en; i++) {
        scanf("<%d, %d, %d>", &from, &to, &weight);
        SetEdge(from, to, weight);
    }

    // 运行Dijkstra算法
    Dijkstra(s, len, p);

    // 输出结果
    for (i = 0; i < vn; i++) {
        printf("<%d, %d, %d>\n", i, len[i], p[i]);
    }

    return 0;
}