c 语言数据结构最短路径

C语言中实现最短路径算法需要用到数据结构，常见的实现方式是使用图和堆这两种数据结构。

在图中，我们可以使用邻接矩阵或邻接表来存储图的信息。对于最短路径算法，经典的算法有Dijkstra算法和Bellman-Ford算法。其中，Dijkstra算法适用于没有负权边的图，而Bellman-Ford算法适用于存在负权边的图。

在堆中，我们可以使用二叉堆或斐波那契堆来实现。堆可以帮助我们快速地找到距离起点最近的节点，从而快速地更新节点的距离值。这样，我们就可以使用贪心算法来逐渐扩展最短路径。

以下是使用Dijkstra算法来实现最短路径的C语言代码示例：

// 邻接矩阵存储图
#define MAX_V 1000
#define INF 1000000000

int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;

void dijkstra(int s) {
  for (int i = 0; i < V; i++) {
    d[i] = INF;
    used[i] = false;
  }
  d[s] = 0;

  while (true) {
    int v = -1;
    for (int u = 0; u < V; u++) {
      if (!used[u] && (v == -1 || d[u] < d[v])) {
        v = u;
      }
    }
    if (v == -1) {
      break;
    }
    used[v] = true;

    for (int u = 0; u < V; u++) {
      d[u] = min(d[u], d[v] + cost[v][u]);
    }
  }
}

在这个代码中，我们使用邻接矩阵存储图的信息，使用一个数组d来记录起点到各个节点的距离，使用一个布尔型数组used来记录哪些节点已经被访问过。在每一次循环中，我们找到距离起点最近的节点v，然后将v标记为已经访问过。然后，我们通过v更新所有与v相邻的节点u的距离值，如果更新后的距离值比原来的距离值更小，那么我们就更新d[u]的值。最后，当所有节点都被访问过之后，d数组中的值就是起点到各个节点的最短距离。