qt用优化队列实现dijkstra

Dijkstra算法是一种用于寻找带权图中单源最短路径的算法。它的基本思想是从起点开始，不断地选择当前最短路径的顶点，直到到达终点或者无法继续搜索为止。

在实现Dijkstra算法时，可以使用优先队列来优化算法的效率。具体实现步骤如下：

1. 定义一个优先队列，用于保存待处理的顶点及其到起点的最短距离。

2. 将起点加入优先队列，距离为0。

3. 不断从优先队列中取出距离起点最近的顶点，将其标记为已处理。

4. 遍历该顶点的所有邻居，并更新它们到起点的距离。

5. 如果某个邻居的距离被更新了，则将其加入优先队列中。

6. 重复步骤3-5，直到优先队列为空或者终点被处理。

7. 如果终点被处理，则返回终点到起点的最短距离，否则说明起点无法到达终点。

下面是一个使用优先队列实现Dijkstra算法的示例代码：

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

using namespace std;

const int INF = numeric_limits<int>::max();

// 定义边的结构体
struct Edge {
    int to; // 目标顶点
    int weight; // 权重
    Edge(int t, int w) : to(t), weight(w) {}
};

// 定义图的邻接表表示法
using Graph = vector<vector<Edge>>;

// Dijkstra算法
vector<int> dijkstra(const Graph& graph, int start) {
    vector<int> dist(graph.size(), INF); // 到起点的距离
    dist[start] = 0;

    // 定义优先队列，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.emplace(0, start);

    while (!q.empty()) {
        auto [d, v] = q.top(); q.pop();
        if (d > dist[v]) continue; // 已经处理过该顶点

        for (auto& e : graph[v]) {
            if (dist[e.to] > dist[v] + e.weight) {
                dist[e.to] = dist[v] + e.weight;
                q.emplace(dist[e.to], e.to);
            }
        }
    }

    return dist;
}

int main() {
    // 构建图
    Graph graph(5);
    graph[0].emplace_back(1, 2);
    graph[0].emplace_back(2, 5);
    graph[1].emplace_back(2, 2);
    graph[1].emplace_back(3, 4);
    graph[1].emplace_back(4, 1);
    graph[2].emplace_back(3, 1);
    graph[2].emplace_back(4, 3);
    graph[3].emplace_back(4, 4);

    auto dist = dijkstra(graph, 0);

    for (int i = 0; i < dist.size(); ++i) {
        cout << "dist[" << i << "] = " << dist[i] << endl;
    }

    return 0;
}

在这个示例代码中，我们使用了C++17中的结构化绑定语法（即`auto [d, v] = q.top()`）来方便地获取优先队列中的元素。同时，我们使用了C++11中的`emplace`函数来避免不必要的拷贝操作，提高效率。