c语言公交最优路径查询数据结构,c语言公交最优路径查询数据结构(附完整代码)

该问题可以使用Dijkstra算法来解决，Dijkstra算法是一种贪心算法，用于解决带有非负权重的图的单源最短路径问题。

首先，我们需要定义一个结构体来表示每个节点：

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    int vertex;
    int distance;
    int predecessor;
    int visited;
    Edge edges[MAX_EDGES];
    int edge_count;
} Node;

其中，`vertex`表示节点的编号，`distance`表示从起点到该节点的最短距离，`predecessor`表示从起点到该节点的最短路径上该节点的前一个节点，`visited`表示该节点是否已经被访问过，`edges`表示该节点与其他节点之间的边，`edge_count`表示该节点有多少个邻居节点。

然后，我们需要构建图。这里我们假设所有节点之间的边都是双向的，即如果节点A到节点B有一条边，那么节点B到节点A也有一条边。我们将图表示为一个节点数组，每个节点包含了它与其他节点之间的边。

Node graph[MAX_NODES];
int node_count = 0;

void add_edge(int from, int to, int weight) {
    graph[from].edges[graph[from].edge_count].vertex = to;
    graph[from].edges[graph[from].edge_count].weight = weight;
    graph[from].edge_count++;
}

接下来，我们需要实现Dijkstra算法。我们用一个堆来存储所有未访问过的节点，每次从堆中取出距离起点最近的节点进行处理，然后将该节点的邻居节点加入堆中。

int heap[MAX_NODES];
int heap_count = 0;

void heap_push(int vertex) {
    heap[heap_count] = vertex;
    int child = heap_count;
    int parent = (child - 1) / 2;
    while (child > 0 && graph[heap[parent]].distance > graph[vertex].distance) {
        heap[child] = heap[parent];
        child = parent;
        parent = (child - 1) / 2;
    }
    heap[child] = vertex;
    heap_count++;
}

int heap_pop() {
    int vertex = heap[0];
    heap_count--;
    heap[0] = heap[heap_count];
    int parent = 0;
    int child = 1;
    while (child < heap_count) {
        if (child + 1 < heap_count && graph[heap[child + 1]].distance < graph[heap[child]].distance) {
            child++;
        }
        if (graph[heap[parent]].distance <= graph[heap[child]].distance) {
            break;
        }
        int temp = heap[parent];
        heap[parent] = heap[child];
        heap[child] = temp;
        parent = child;
        child = parent * 2 + 1;
    }
    return vertex;
}

void dijkstra(int start) {
    for (int i = 0; i < node_count; i++) {
        graph[i].distance = INT_MAX;
        graph[i].visited = 0;
        graph[i].predecessor = -1;
    }
    graph[start].distance = 0;
    heap_push(start);

    while (heap_count > 0) {
        int vertex = heap_pop();
        if (graph[vertex].visited) {
            continue;
        }
        graph[vertex].visited = 1;
        for (int i = 0; i < graph[vertex].edge_count; i++) {
            int neighbor = graph[vertex].edges[i].vertex;
            if (!graph[neighbor].visited) {
                int distance = graph[vertex].distance + graph[vertex].edges[i].weight;
                if (distance < graph[neighbor].distance) {
                    graph[neighbor].distance = distance;
                    graph[neighbor].predecessor = vertex;
                    heap_push(neighbor);
                }
            }
        }
    }
}

最后，我们可以通过调用`dijkstra`函数来求出最短路径。在该函数返回后，每个节点的`distance`字段将包含从起点到该节点的最短距离，`predecessor`字段将包含从起点到该节点的最短路径上该节点的前一个节点。

完整代码如下：