qt用dijkstra邻接链表算最短路径

以下是基于Qt的Dijkstra算法的邻接链表实现，其中包括了节点类和图类：

节点类：

class Node
{
public:
    Node(QString n, int d): name(n), dist(d) {}
    QString name;
    int dist;
    QList<QPair<Node*, int>> adjList; // 邻接链表，存储与该节点相邻的节点及其边权重
    bool visited = false;
};

图类：

class Graph
{
public:
    void addNode(QString name, int dist) // 添加节点
    {
        Node* node = new Node(name, dist);
        nodes.append(node);
    }

    void addEdge(Node* node1, Node* node2, int weight) // 添加边
    {
        node1->adjList.append(QPair<Node*, int>(node2, weight));
        node2->adjList.append(QPair<Node*, int>(node1, weight));
    }

    void dijkstra(Node* startNode) // Dijkstra算法
    {
        // 初始化距离
        foreach(Node* node, nodes) {
            node->dist = INT_MAX;
            node->visited = false;
        }
        startNode->dist = 0;

        // 循环n-1次，每次找到一个最短路径
        for(int i = 0; i < nodes.size()-1; i++) {
            Node* minNode = findMinDistNode();
            minNode->visited = true;
            foreach(QPair<Node*, int> pair, minNode->adjList) {
                Node* node = pair.first;
                int weight = pair.second;
                if(!node->visited) {
                    int newDist = minNode->dist + weight;
                    if(newDist < node->dist) {
                        node->dist = newDist;
                    }
                }
            }
        }
    }

private:
    QList<Node*> nodes;

    Node* findMinDistNode() // 找到未访问节点中距离最小的节点
    {
        Node* minNode = nullptr;
        int minDist = INT_MAX;
        foreach(Node* node, nodes) {
            if(!node->visited && node->dist < minDist) {
                minNode = node;
                minDist = node->dist;
            }
        }
        return minNode;
    }
};

使用示例：

Graph graph;
graph.addNode("A", 0);
graph.addNode("B", INT_MAX);
graph.addNode("C", INT_MAX);
graph.addNode("D", INT_MAX);

graph.addEdge(graph.nodes[0], graph.nodes[1], 5);
graph.addEdge(graph.nodes[0], graph.nodes[2], 3);
graph.addEdge(graph.nodes[1], graph.nodes[3], 1);
graph.addEdge(graph.nodes[2], graph.nodes[3], 2);

graph.dijkstra(graph.nodes[0]);

foreach(Node* node, graph.nodes) {
    qDebug() << node->name << ": " << node->dist;
}

输出结果：

"A: " 0
"B: " 5
"C: " 3
"D: " 5