C语言实现Dijkstra算法计算最短路径

"该文档提供了一个使用C语言实现的Dijkstra算法示例，结合邻接矩阵来计算图中节点间的最短路径。" 在计算机科学领域，图算法是解决复杂问题的重要工具，其中Dijkstra算法是一种广泛应用的单源最短路径算法。这个算法由荷兰计算机科学家艾兹格·迪科斯彻提出，主要用于找到带权重的有向图或无向图中从源节点到其他所有节点的最短路径。 在给定的代码中，首先定义了一个名为`Graph`的结构体，用于存储图的相关信息，包括顶点数`n`、边数`m`以及邻接矩阵`adj_matrix`。邻接矩阵是一个二维数组，用于表示图中各节点之间的连接关系和权重。例如，`adj_matrix[i*n+j]`表示节点i到节点j的边的权重，如果不存在边，则设置为`INT_MAX`表示无穷大。 接着，`init_adj_matrix`函数用于初始化邻接矩阵，将所有元素设为`INT_MAX`，表示没有直接相连的节点之间距离视为无穷大。`insert_edge`函数则用于在图中插入边，同时更新邻接矩阵，确保双向边的权重一致。 核心部分是`dijkstra`函数，它实现了Dijkstra算法。该算法的基本思想是使用优先队列（这里使用了简单数组模拟）维护未访问的节点，并按照当前估计的最短路径长度进行排序。初始时，源节点的距离设为0，其他节点距离设为无穷大。在每一步，算法选择距离最小的节点并更新其相邻节点的距离。当优先队列为空或源节点已被访问时，算法结束。 在`dijkstra`函数中，`visited`数组用于标记已访问的节点，`pq`数组模拟优先队列，`heap_size`记录当前队列大小。`heapify`函数用于调整优先队列，确保队首始终是最小值。`while`循环中，每次选择队首节点u，如果该节点已访问则跳过，否则标记为已访问，并更新与其相邻节点的距离。 通过这样的过程，Dijkstra算法可以有效地找到源节点到图中所有其他节点的最短路径。注意，这个实现仅适用于非负权重的边，因为Dijkstra算法在边权重为负值的情况下可能无法得到正确结果。如果图中存在负权边，可以考虑使用其他算法，如Bellman-Ford算法。