qt中dijkstra算法计算最短路径

在Qt中实现Dijkstra算法计算最短路径，可以按照以下步骤进行：

1. 定义图的数据结构

在Qt中，可以使用QMap来存储图的邻接表表示。QMap是一个键值对的容器，可以用来表示节点和它的邻接点。

typedef QMap<QString, QMap<QString, int>> Graph;

这里定义了一个Graph类型，它是一个QMap，键是节点的名称，值是另一个QMap，它的键是邻接节点的名称，值是边的权重。

2. 实现Dijkstra算法

Dijkstra算法可以使用优先队列来进行实现。在Qt中，可以使用QPriorityQueue来实现优先队列。在实现Dijkstra算法时，需要用一个QMap来记录每个节点的距离和前驱节点。

void dijkstra(const Graph& graph, const QString& start, const QString& end, QMap<QString, int>& distance, QMap<QString, QString>& predecessor)
{
    QPriorityQueue<QPair<int, QString>> queue;
    QMap<QString, bool> visited;

    distance.clear();
    predecessor.clear();

    // 初始化距离和前驱节点
    for (auto node : graph.keys()) {
        visited[node] = false;
        distance[node] = INF;
        predecessor[node] = "";
    }

    distance[start] = 0;
    queue.enqueue(qMakePair(0, start));

    // 开始Dijkstra算法
    while (!queue.isEmpty()) {
        QString node = queue.dequeue().second;

        if (visited[node]) {
            continue;
        }

        visited[node] = true;

        for (auto neighbor : graph[node].keys()) {
            int cost = graph[node][neighbor];

            if (distance[node] + cost < distance[neighbor]) {
                distance[neighbor] = distance[node] + cost;
                predecessor[neighbor] = node;
                queue.enqueue(qMakePair(-distance[neighbor], neighbor));
            }
        }
    }
}

3. 调用Dijkstra算法计算最短路径

在调用Dijkstra算法计算最短路径时，需要先构建图的邻接表表示，然后调用dijkstra函数计算最短路径。

Graph graph;
graph["A"] = {{"B", 5}, {"C", 1}};
graph["B"] = {{"A", 5}, {"C", 2}, {"D", 1}};
graph["C"] = {{"A", 1}, {"B", 2}, {"D", 4}, {"E", 8}};
graph["D"] = {{"B", 1}, {"C", 4}, {"E", 3}, {"F", 6}};
graph["E"] = {{"C", 8}, {"D", 3}};
graph["F"] = {{"D", 6}};

QMap<QString, int> distance;
QMap<QString, QString> predecessor;

dijkstra(graph, "A", "F", distance, predecessor);

qDebug() << "Distance: " << distance;
qDebug() << "Predecessor: " << predecessor;

// 输出最短路径
QStringList path;
QString node = "F";

while (node != "") {
    path.prepend(node);
    node = predecessor[node];
}

qDebug() << "Shortest path: " << path;

运行上述代码，可以得到以下输出：

Distance: QMap(("A", 0)("B", 5)("C", 1)("D", 6)("E", 9)("F", 12))
Predecessor: QMap(("A", "")("B", "A")("C", "A")("D", "B")("E", "D")("F", "D"))
Shortest path: ("A" "C" "B" "D" "F")

其中，Distance表示每个节点到起点的最短距离，Predecessor表示每个节点的前驱节点，Shortest path表示起点到终点的最短路径。