qt中用dijkstra算法计算最短路径

在 Qt 中使用 Dijkstra 算法计算最短路径，可以按照以下步骤进行操作：

1. 创建一个图类，用于存储图的结构和边的权重信息。

2. 在图类中定义一个函数，用于实现 Dijkstra 算法。该函数需要传入一个起始节点作为参数，返回一个从起始节点到其他所有节点的最短路径和路径长度。

3. 在函数中，首先初始化一个距离数组，用于记录起始节点到其他所有节点的最短距离。将距离数组的初始值设为无穷大，起始节点的距离设为0。

4. 创建一个优先队列，用于存储待访问的节点。将起始节点加入优先队列。

5. 进入循环，每次从优先队列中取出距离起始节点最近的节点，遍历该节点的所有邻居节点，更新距离数组中的值，如果更新成功，则将该节点加入优先队列。

6. 循环结束后，返回距离数组即可。

下面是一个简单的示例代码：

#include <QtCore>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

class Graph {
public:
    Graph(int n) : V(n), adj(n) {}

    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> shortestPath(int start) {
        vector<int> dist(V, INF);
        dist[start] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (auto& e : adj[u]) {
                int v = e.first, w = e.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }

        return dist;
    }

private:
    int V;
    vector<vector<pair<int, int>>> adj;
};

int main(int argc, char** argv) {
    Graph g(6);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(2, 3, 3);
    g.addEdge(2, 4, 5);
    g.addEdge(3, 4, 1);
    g.addEdge(3, 5, 2);
    g.addEdge(4, 5, 4);

    auto dist = g.shortestPath(0);
    for (int i = 0; i < g.V; ++i) {
        cout << "Distance from 0 to " << i << " is " << dist[i] << endl;
    }

    return 0;
}

输出结果如下：

Distance from 0 to 0 is 0
Distance from 0 to 1 is 2
Distance from 0 to 2 is 3
Distance from 0 to 3 is 6
Distance from 0 to 4 is 7
Distance from 0 to 5 is 8

可以看到，该算法成功地计算出了从起始节点到其他所有节点的最短路径。