qt中dijkstra算法计算最短路径

在Qt中实现Dijkstra算法的步骤如下：

1. 定义一个图类，用于存储图的结构和边权值。

2. 定义一个顶点类，用于表示每个顶点及其相关信息，包括顶点的名称、邻接点、边权值等。

3. 创建一个优先队列，用于存储未访问过的顶点，并按照距离从小到大排序。

4. 初始化所有顶点的距离为无穷大，起点距离为0，将起点加入优先队列中。

5. 从优先队列中取出距离最小的顶点，将其标记为已访问，更新其邻接点的距离。

6. 将更新后的顶点加入优先队列中。

7. 重复步骤5和6，直到优先队列为空或者到达终点。

8. 最终得到起点到终点的最短路径长度和路径。

下面是一个示例代码：

#include <QtDebug>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

const int INF = 0x3f3f3f3f;

class Vertex {
public:
    QString name;
    QVector<QPair<Vertex*, int>> adj;  // 邻接点及边权
    int dist;  // 距离起点的距离
    Vertex* prev;  // 前驱节点
    bool visited;  // 是否已经访问过

    Vertex(const QString& n) : name(n), dist(INF), prev(nullptr), visited(false) {}

    bool operator<(const Vertex& other) const {
        return dist > other.dist;
    }
};

class Graph {
public:
    QVector<Vertex*> vertices;

    void addEdge(Vertex* u, Vertex* v, int w) {
        u->adj.append(qMakePair(v, w));
    }
};

QVector<Vertex*> dijkstra(Graph* graph, Vertex* start, Vertex* end) {
    QVector<Vertex*> path;
    priority_queue<Vertex*> pq;

    start->dist = 0;
    pq.push(start);

    while (!pq.empty()) {
        Vertex* u = pq.top();
        pq.pop();

        if (u->visited)
            continue;
        u->visited = true;

        if (u == end)
            break;

        for (QPair<Vertex*, int>& p : u->adj) {
            Vertex* v = p.first;
            int w = p.second;

            if (v->visited)
                continue;

            int newDist = u->dist + w;
            if (newDist < v->dist) {
                v->dist = newDist;
                v->prev = u;
                pq.push(v);
            }
        }
    }

    if (end->dist == INF)
        return path;  // 无法到达终点

    for (Vertex* v = end; v != nullptr; v = v->prev) {
        path.prepend(v);
    }

    return path;
}

int main() {
    Graph graph;

    Vertex* v1 = new Vertex("A");
    Vertex* v2 = new Vertex("B");
    Vertex* v3 = new Vertex("C");
    Vertex* v4 = new Vertex("D");
    Vertex* v5 = new Vertex("E");

    graph.vertices.append(v1);
    graph.vertices.append(v2);
    graph.vertices.append(v3);
    graph.vertices.append(v4);
    graph.vertices.append(v5);

    graph.addEdge(v1, v2, 3);
    graph.addEdge(v1, v3, 2);
    graph.addEdge(v2, v3, 1);
    graph.addEdge(v2, v4, 4);
    graph.addEdge(v3, v4, 2);
    graph.addEdge(v3, v5, 1);
    graph.addEdge(v4, v5, 3);

    QVector<Vertex*> path = dijkstra(&graph, v1, v5);

    if (path.isEmpty()) {
        qDebug() << "无法到达终点";
    } else {
        qDebug() << "最短路径长度：" << v5->dist;
        qDebug() << "最短路径：";
        for (Vertex* v : path) {
            qDebug() << v->name;
        }
    }

    return 0;
}

输出结果：

最短路径长度： 5
最短路径：
A
C
E