迪杰斯特拉算法C代码

以下是使用C语言实现的迪杰斯特拉算法的代码示例：

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

#define MAX_NODES 100

// 结点的数据结构
typedef struct {
    int cost; // 距离起始节点的最短距离
    int visited; // 是否已经被访问过
    int prev_node; // 前一个节点
} Node;

// 迪杰斯特拉算法函数
void dijkstra(int graph[MAX_NODES][MAX_NODES], int num_nodes, int start_node) {
    Node nodes[MAX_NODES]; // 存储所有节点的信息
    int i, j;
    
    // 初始化节点信息
    for (i = 0; i < num_nodes; i++) {
        nodes[i].cost = INT_MAX;
        nodes[i].visited = 0;
        nodes[i].prev_node = -1;
    }

    nodes[start_node].cost = 0; // 起始节点到自身的距离为0
    for (i = 0; i < num_nodes; i++) {
        int min_cost = INT_MAX;
        int min_node = -1;

        // 找到当前距离起始节点最近的未访问节点
        for (j = 0; j < num_nodes; j++) {
            if (!nodes[j].visited && nodes[j].cost < min_cost) {
                min_cost = nodes[j].cost;
                min_node = j;
            }
        }

        if (min_node == -1) {
            break; // 所有节点都已经访问过，退出循环
        }

        nodes[min_node].visited = 1; // 将最近的节点标记为已访问

        // 更新与最近节点相邻节点的距离
        for (j = 0; j < num_nodes; j++) {
            if (graph[min_node][j] != 0 && nodes[j].visited == 0) {
                int new_cost = nodes[min_node].cost + graph[min_node][j];
                if (new_cost < nodes[j].cost) {
                    nodes[j].cost = new_cost;
                    nodes[j].prev_node = min_node;
                }
            }
        }
    }

    // 输出最短路径
    for (i = 0; i < num_nodes; i++) {
        printf("Node %d: Cost = %d, Previous Node = %d\n", i, nodes[i].cost, nodes[i].prev_node);
    }
}

int main() {
    int graph[MAX_NODES][MAX_NODES]; // 图的邻接矩阵
    int num_nodes, start_node;
    int i, j;

    printf("Enter the number of nodes: ");
    scanf("%d", &num_nodes);

    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < num_nodes; i++) {
        for (j = 0; j < num_nodes; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    printf("Enter the start node: ");
    scanf("%d", &start_node);

    dijkstra(graph, num_nodes, start_node);

    return 0;
}

这段代码实现了迪杰斯特拉算法，通过输入图的邻接矩阵和起始节点，输出每个节点到起始节点的最短距离和前一个节点。请注意，这只是一个简单的实现示例，实际应用中可能需要根据具体情况进行适当修改。