dijkstra算法c语言graph

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，它可以用C语言实现。在实现Dijkstra算法时，需要使用图来表示问题，并使用优先队列来维护当前最短路径的节点。

在C语言中，可以使用结构体来表示图中的节点和边，例如：

typedef struct {
    int dest;   // 目标节点
    int weight; // 边的权重
} Edge;

typedef struct {
    Edge* edges; // 边的数组
    int numEdges; // 边的数量
} Node;

typedef struct {
    Node* nodes; // 节点的数组
    int numNodes; // 节点的数量
} Graph;

在实现Dijkstra算法时，需要使用一个数组来记录每个节点的最短路径长度和前驱节点，例如：

typedef struct {
    int dist;   // 最短路径长度
    int prev;   // 前驱节点
    bool visited; // 是否已访问
} DijkstraData;

然后，可以使用优先队列来维护当前最短路径的节点，例如：

typedef struct {
    int node;   // 节点编号
    int dist;   // 最短路径长度
} PQNode;

typedef struct {
    PQNode* nodes;  // 节点的数组
    int size;       // 队列的大小
    int capacity;   // 队列的容量
} PriorityQueue;

最后，可以使用以下代码来实现Dijkstra算法：

void dijkstra(Graph* graph, int start, DijkstraData* data) {
    PriorityQueue pq;
    pq.nodes = (PQNode*) malloc(sizeof(PQNode) * graph->numNodes);
    pq.size = ;
    pq.capacity = graph->numNodes;

    for (int i = ; i < graph->numNodes; i++) {
        data[i].dist = INT_MAX;
        data[i].prev = -1;
        data[i].visited = false;
    }

    data[start].dist = ;

    PQNode startNode = { start,  };
    pqPush(&pq, startNode);

    while (!pqIsEmpty(&pq)) {
        PQNode node = pqPop(&pq);

        if (data[node.node].visited) {
            continue;
        }

        data[node.node].visited = true;

        for (int i = ; i < graph->nodes[node.node].numEdges; i++) {
            Edge edge = graph->nodes[node.node].edges[i];
            int dest = edge.dest;
            int weight = edge.weight;

            if (data[dest].visited) {
                continue;
            }

            int newDist = data[node.node].dist + weight;

            if (newDist < data[dest].dist) {
                data[dest].dist = newDist;
                data[dest].prev = node.node;

                PQNode destNode = { dest, newDist };
                pqPush(&pq, destNode);
            }
        }
    }

    free(pq.nodes);
}

其中，pqPush和pqPop函数可以使用堆来实现。