qt用dijkstra邻接链表算最短路径

以下是Qt中使用Dijkstra算法和邻接链表来计算最短路径的示例代码：

// 定义邻接链表结构体
struct Edge {
    int dest;
    int weight;
    Edge* next;
};

// 定义Dijkstra算法函数
void dijkstra(int start, QVector<Edge*>& graph, QVector<int>& distance) {
    distance.fill(INT_MAX); // 初始化距离为无穷大
    distance[start] = 0; // 起点距离为0

    QSet<int> visited; // 已访问节点集合
    visited.insert(start);

    QQueue<int> queue; // 待访问节点队列
    queue.enqueue(start);

    while (!queue.isEmpty()) {
        int curr = queue.dequeue();
        visited.insert(curr);

        // 遍历邻接链表中curr节点的所有边
        Edge* edge = graph[curr];
        while (edge) {
            int dest = edge->dest;
            int weight = edge->weight;

            // 更新距离
            if (!visited.contains(dest) && distance[curr] + weight < distance[dest]) {
                distance[dest] = distance[curr] + weight;
            }

            // 将未访问过的节点加入待访问队列
            if (!visited.contains(dest)) {
                queue.enqueue(dest);
            }

            edge = edge->next;
        }
    }
}

// 示例代码
int main() {
    // 构建邻接链表
    QVector<Edge*> graph(n);
    for (int i = 0; i < n; i++) {
        graph[i] = nullptr;
    }

    for (int i = 0; i < m; i++) {
        int u, v, w;
        // 读入边的信息

        // 添加u->v的边
        Edge* edge1 = new Edge({v, w, graph[u]});
        graph[u] = edge1;

        // 添加v->u的边
        Edge* edge2 = new Edge({u, w, graph[v]});
        graph[v] = edge2;
    }

    // 计算最短路径
    QVector<int> distance(n);
    dijkstra(start, graph, distance);

    // 输出结果
    for (int i = 0; i < n; i++) {
        qDebug() << "Distance from" << start << "to" << i << ":" << distance[i];
    }

    // 释放内存
    for (int i = 0; i < n; i++) {
        Edge* edge = graph[i];
        while (edge) {
            Edge* next = edge->next;
            delete edge;
            edge = next;
        }
    }

    return 0;
}