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>

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

#define INF INT_MAX // 定义正无穷

typedef struct {
    int weight; // 权值
    int next; // 下一个结点
} Edge;

typedef struct {
    int vertex; // 顶点
    int dist; // 最短距离
    int prev; // 前驱结点
} Node;

void Dijkstra(int vn, int en, int s, Edge **graph) {
    int i, j, u, min_dist;
    Edge *p;
    Node *nodes = (Node *)malloc(sizeof(Node) * vn); // 存储各结点的信息
    int *visited = (int *)malloc(sizeof(int) * vn); // 标记结点是否被访问过

    // 初始化
    for (i = 0; i < vn; i++) {
        nodes[i].vertex = i;
        nodes[i].dist = INF;
        nodes[i].prev = s;
        visited[i] = 0;
    }
    nodes[s].dist = 0;

    // 找到最短距离的结点
    for (i = 0; i < vn; i++) {
        min_dist = INF;
        u = -1;
        for (j = 0; j < vn; j++) {
            if (!visited[j] && nodes[j].dist < min_dist) {
                min_dist = nodes[j].dist;
                u = j;
            }
        }
        if (u == -1) break;
        visited[u] = 1;

        // 更新与u相邻的结点的最短距离
        for (p = graph[u]; p != NULL; p = p->next) {
            if (!visited[p->next] && nodes[u].dist + p->weight < nodes[p->next].dist) {
                nodes[p->next].dist = nodes[u].dist + p->weight;
                nodes[p->next].prev = u;
            }
        }
    }

    // 输出结果
    for (i = 0; i < vn; i++) {
        printf("<%d, %d, %d>\n", nodes[i].vertex, nodes[i].dist, nodes[i].prev);
    }

    free(nodes);
    free(visited);
}

int main() {
    int vn, en, s, i, from, to, weight;
    Edge **graph;

    scanf("%d %d %d", &vn, &en, &s);

    // 初始化邻接表
    graph = (Edge **)malloc(sizeof(Edge *) * vn);
    for (i = 0; i < vn; i++) {
        graph[i] = NULL;
    }

    // 读入边
    for (i = 0; i < en; i++) {
        scanf("<%d, %d, %d>", &from, &to, &weight);
        Edge *p = graph[from];
        while (p != NULL && p->next != to) {
            p = p->next;
        }
        if (p == NULL) {
            Edge *new_edge = (Edge *)malloc(sizeof(Edge));
            new_edge->weight = weight;
            new_edge->next = to;
            new_edge->next = graph[from];
            graph[from] = new_edge;
        } else {
            p->weight = weight;
        }
    }

    Dijkstra(vn, en, s, graph);

    // 释放内存
    for (i = 0; i < vn; i++) {
        Edge *p = graph[i];
        while (p != NULL) {
            Edge *temp = p;
            p = p->next;
            free(temp);
        }
    }
    free(graph);

    return 0;
}