qt中dijkstra算法计算最短路径

在Qt中实现Dijkstra算法可以分为以下几个步骤：

1. 定义节点类

class Node {
public:
    QString name;  // 节点名称
    QVector<QPair<Node*, int>> neighbors;  // 相邻节点及其边权值
    int distance = INT_MAX;  // 起点到该节点的距离
    bool visited = false;  // 是否已访问

    Node(const QString& name) : name(name) {}
};

2. 定义图类

class Graph {
public:
    QVector<Node*> nodes;  // 所有节点

    void addNode(Node* node) {
        nodes.append(node);
    }

    void addEdge(Node* from, Node* to, int weight) {
        from->neighbors.append(qMakePair(to, weight));
        to->neighbors.append(qMakePair(from, weight));  // 无向图
    }
};

3. 实现Dijkstra算法

void dijkstra(Graph* graph, Node* start) {
    // 初始化
    for (auto node : graph->nodes) {
        node->distance = INT_MAX;
        node->visited = false;
    }
    start->distance = 0;

    // 运行Dijkstra算法
    QSet<Node*> unvisitedNodes;
    unvisitedNodes.insert(graph->nodes.begin(), graph->nodes.end());
    while (!unvisitedNodes.isEmpty()) {
        // 从未访问节点中选取距离最小的节点
        Node* minNode = nullptr;
        for (auto node : unvisitedNodes) {
            if (!minNode || node->distance < minNode->distance) {
                minNode = node;
            }
        }
        unvisitedNodes.remove(minNode);
        minNode->visited = true;

        // 更新相邻节点的距离
        for (auto neighbor : minNode->neighbors) {
            if (!neighbor.first->visited) {
                int dist = minNode->distance + neighbor.second;
                if (dist < neighbor.first->distance) {
                    neighbor.first->distance = dist;
                }
            }
        }
    }
}

4. 调用Dijkstra算法

Graph* graph = new Graph();
Node* n1 = new Node("A");
Node* n2 = new Node("B");
Node* n3 = new Node("C");
Node* n4 = new Node("D");
graph->addNode(n1);
graph->addNode(n2);
graph->addNode(n3);
graph->addNode(n4);
graph->addEdge(n1, n2, 1);
graph->addEdge(n1, n3, 3);
graph->addEdge(n2, n3, 1);
graph->addEdge(n2, n4, 4);
graph->addEdge(n3, n4, 1);
dijkstra(graph, n1);
qDebug() << n1->distance << n2->distance << n3->distance << n4->distance;

以上代码实现了一个简单的无向图，并调用Dijkstra算法计算从节点A到其他节点的最短距离。