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

下面是使用Dijkstra算法以邻接链表的形式实现最短路径的示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

// 邻接链表中的边结构体
struct Edge {
    int to;     // 目标节点
    int weight; // 边权重
    Edge(int t, int w): to(t), weight(w) {}
};

// 邻接链表中的节点结构体
struct Node {
    int id;             // 节点编号
    int distance;       // 起点到该节点的最短距离
    vector<Edge> edges; // 与该节点相连的边
    bool operator<(const Node& other) const { // 定义小于运算符，用于优先队列中
        return distance > other.distance;
    }
};

// 计算起点到所有节点的最短路径
vector<int> dijkstra(vector<Node>& graph, int start) {
    vector<int> distances(graph.size(), INT_MAX); // 起点到每个节点的最短距离
    distances[start] = 0;                         // 起点到自己的距离为0

    priority_queue<Node> pq;
    pq.push({start, 0, graph[start].edges});

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();

        if (distances[node.id] < node.distance) continue; // 优化1：如果已经处理过该节点，则忽略

        distances[node.id] = node.distance;

        for (Edge edge : node.edges) {
            int newDist = node.distance + edge.weight;
            if (newDist < distances[edge.to]) {
                pq.push({edge.to, newDist, graph[edge.to].edges});
                distances[edge.to] = newDist;
            }
        }
    }

    return distances;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<Node> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].edges.push_back({v, w});
        graph[v].edges.push_back({u, w});
    }

    vector<int> distances = dijkstra(graph, 0);

    for (int i = 0; i < n; i++) {
        cout << "Distance from 0 to " << i << " is " << distances[i] << endl;
    }

    return 0;
}

在上述代码中，我们首先定义了邻接链表中的边和节点结构体，然后实现了计算起点到所有节点的最短路径的dijkstra函数。在函数中，我们使用一个优先队列来保存待处理的节点，并根据节点与起点的距离从小到大排序。在每次处理队首节点时，我们更新与该节点相连的所有节点的最短距离，并将它们加入优先队列中。在处理完所有节点后，我们返回起点到所有节点的最短距离。

在main函数中，我们首先读取输入的节点数量和边数量，并根据输入构造邻接链表。然后调用dijkstra函数，计算起点到所有节点的最短距离，并输出结果。

需要注意的是，由于STL中的优先队列使用堆实现，每次插入和删除元素的时间复杂度为O(log n)，因此总时间复杂度为O((m + n) log n)，其中m为边数，n为节点数。